public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix == null  matrix.length == 0)
return false;
return searchMatrixHelper(matrix, 0, matrix[0].length1, 0, matrix.length1, target);
}
public boolean searchMatrixHelper(int[][] matrix, int xs, int xl, int ys, int yl, int target){
if(xs > xl  ys > yl)
return false;
int xSmall = xs;
while(xs <= xl){
int m = (xs + xl)/2;
if(matrix[ys][m] == target)
return true;
else if(matrix[ys][m] > target)
xl = m  1;
else
xs = m + 1;
}
int ySmall = ys;
while(ys <= yl){
int m = (ys + yl)/2;
if(matrix[m][xSmall] == target)
return true;
else if(matrix[m][xSmall] > target)
yl = m  1;
else
ys = m + 1;
}
return searchMatrixHelper(matrix, xSmall+1, xl, ySmall+1, yl, target);
}
}
How about this java AC answer?


Just a little explanation. For example,
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
and the target is 5.
1st call to helper would be on the whole matrix itself;
During 1st call, it would find the biggest number on the first column that is smaller than target, which is 3. Then it would find the biggest number on the first row that is smaller than target, which is 7.2nd call to helper would be on a subset of the matrix that cuts off 1st and last two rows, as well as 1st and last two columns, i.e.
[ [ 5 ], [ 6 ], ]
During the 2nd call, the target is found.