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..}