```
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) return false;
return helpSearch(matrix, target, 0, 0, matrix.length-1, matrix[0].length-1);
}
private boolean helpSearch(int[][] matrix, int target, int r1, int c1, int r2, int c2) {
if (r1 > r2 || c1 > c2) return false;
if (r1 == r2 && c1 == c2) return matrix[r1][c1] == target;
int l = r1;
int r = r2;
while (l < r) {
int mid = (l+r+1)/2;
if (matrix[mid][c1] == target) return true;
if (matrix[mid][c1] < target) l = mid;
else r = mid-1;
}
r2 = r;
l = c1;
r = c2;
while (l < r) {
int mid = (l+r+1)/2;
if (matrix[r1][mid] == target) return true;
if (matrix[r1][mid] < target) l = mid;
else r = mid-1;
}
c2 = r;
l = r1;
r = r2;
while (l < r) {
int mid = (l+r)/2;
if (matrix[mid][c2] == target) return true;
if (matrix[mid][c2] < target) l = mid+1;
else r = mid;
}
r1 = l;
l = c1;
r = c2;
while (l < r) {
int mid = (l+r)/2;
if (matrix[r2][mid] == target) return true;
if (matrix[r2][mid] < target) l = mid+1;
else r = mid;
}
c1 = l;
return helpSearch(matrix, target, r1, c1, r2, c2);
}
```