题解 | #矩阵元素查找#NC86 CCCC语言

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param mat int整型二维数组 
 * @param matRowLen int mat数组行数
 * @param matColLen int* mat数组列数
 * @param n int整型 
 * @param m int整型 
 * @param x int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int* findElement(int** mat, int matRowLen, int* matColLen, int n, int m, int x, int* returnSize ) {
    // write code here
    *returnSize=2;
    int i=0,j=0,low=0,high=0,mid=(low+high)/2;
    int *returnarray=NULL;
    returnarray=malloc(sizeof(int)*2);                //申请返回数组
    high=n-1;
    while(low<=high){                               //0列找最大可能的行，小于（x,0)，x行及后面都大于查找元素
          mid=(low+high)/2;
          if(x<mat[mid][0]){
              high=mid-1;
              continue;
          }
          else if(x==mat[mid][0]){
            returnarray[0]=mid;
            returnarray[1]=0;
            return returnarray;
          }
          else{
            break;
          }
    }
    while(low<=high){                            //m-1列找最小可能的行，查找值大于（y,m-1)的必定大于y行前面的
          mid=(low+high)/2;
          if(x>mat[mid][m-1]){
              low=mid+1;
              continue;
          }
          else if(x==mat[mid][m-1]){
            returnarray[0]=mid;
            returnarray[1]=m-1;
            return returnarray;
          }
          else{
            break;
          }
    }
    int r=0,l=0;
    for(i=low;i<=high;i++){                      //两个行之间，每行用二分查找，是的话直接返回，否则下一行
        r=m-1;l=0;
        while(l<=r){
          mid=(r+l)/2;
          if(x<mat[i][mid]){
             r=mid-1;
          }
           else if(x>mat[i][mid]){
              l=mid+1;
          }
          else {
              returnarray[0]=i;
               returnarray[1]=mid;
               return returnarray;
          }
        }
    }
    returnarray[1]=high;                                //这里没啥用
    return returnarray;                                 //本题没有考虑找不到，这里随便返回
}