Just share my solution using 2-D binary search searching only 2 regions after every recursive call.

It searches diagonally. One possible optimization is when the matrix is only one row or one column, just use 1-D BS.

public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rs = matrix.length;
if (rs==0) return false;
int cs = matrix[0].length;
if (cs==0) return false;
int r1=0, r2=rs;
int c1=0, c2=cs;
return searchDiagonal(matrix, r1, r2, c1, c2, target);
}
boolean searchDiagonal(int[][] matrix, int r1, int r2, int c1, int c2, int target) {
if (r1==r2||c1==c2) return false;
if (matrix[r2-1][c2-1] == target) return true;
if (matrix[r2-1][c2-1] < target) return false;
if (matrix[r1][c1] > target) return false;
int d = Math.min(r2-r1, c2-c1);
int lo=0;
int hi=d;
while (lo<hi) {
int mid = lo + (hi-lo)/2;
if (matrix[r1+mid][c1+mid] == target) return true;
else if (matrix[r1+mid][c1+mid] > target) {
hi=mid;
} else {
lo=mid+1;
}
}
return searchDiagonal(matrix, r1, r1+lo, c1+lo, c2, target) || searchDiagonal(matrix, r1+lo, r2, c1, c1+lo, target);
}
}