62 在递增二维数组中查找target，要求用Ologn

1.代码

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) { //先找到某一行matrix[i]其中满足 target > matrix[i][0] && target < matrix[i][n-1] int up = 0; int down = matrixSize - 1; int target_row = 0; int flag = 0; int row = matrixSize; int col = matrixColSize[0]; //先二分找到所在行 while(up <= down){ int mid = (up+down)/2; if(target >= matrix[mid][0] && target <= matrix[mid][col-1]){ target_row = mid; flag = 1; break; } if(target > matrix[mid][0]){ up = mid + 1; } if( target < matrix[mid][0]){ down = mid - 1; } } if(flag == 0)//如果没有找到所要的行提前返回 return false; //此时target_row就是target所在的行，继续在matrix[target_row][]数组二分 int left = 0; int right = col - 1; while(left <= right){//等于也要查一次 否则可能漏掉 int mid = (left + right)/2; if(matrix[target_row][mid] == target) return true; if(matrix[target_row][mid] < target){ left = mid +1; } if(matrix[target_row][mid] > target){ right = mid -1; } } return false; }