```
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
return searchRec(matrix, target, 0, 0, matrix.length-1, matrix[0].length-1);
}
private boolean searchRec(int[][] matrix, int target, int loX, int loY, int hiX, int hiY) {
if (loX < 0 || loY < 0 || hiX >= matrix.length || hiY >= matrix[0].length || loX > hiX || loY > hiY) {
return false;
}
if (loX == hiX && loY == hiY) {
return target == matrix[loX][loY];
}
int x = (loX + hiX) / 2;
int y = (loY + hiY) / 2;
boolean result = false;
if (matrix[x][y] >= target) {
result |= searchRec(matrix, target, loX, loY, x, y);
} else {
result |= searchRec(matrix, target, x+1, y+1, hiX, hiY);
}
result |= searchRec(matrix, target, x+1, loY, hiX, y);
result |= searchRec(matrix, target, loX, y+1, x, hiY);
return result;
}
```

}