使用二进制搜索检查二维数组中是否存在元素

Question

编写一个高效的算法来搜索 m x n 矩阵中的值。该矩阵具有以下属性：

每行中的整数从左到右排序。 每行的第一个整数大于上一行的最后一个整数 click for example

Answer 1

public boolean searchMatrix(int[][] matrix, int target) {
    if(matrix.length == 0 || matrix[0].length == 0)
        return false;
    int row = binarySearchRow(matrix,0,matrix.length-1,target);
    return binarySearch(matrix,0,matrix[0].length-1,target,row);
   }

private static int binarySearchRow(int arr[][], int l, int r, int x) { 

        if (r >= l) { 
            int mid = l + (r - l) / 2; 

         //check if element is in between first and last element of that row
            if (x >= arr[mid][0] && x <= arr[mid][arr[0].length-1]) 
                return mid; 

         //if not move on to check other halves
            if (arr[mid][0] > x && arr[mid][arr[0].length-1]>x) 
                return binarySearchRow(arr, l, mid - 1, x); 

                 return binarySearchRow(arr, mid + 1, r, x); 
        } 

    return 0;
}
  public boolean binarySearch(...,row){..apply normal bs here..}