The idea is to recursively compare target with the element in the middle of the matrix and eliminate the quarter of the matrix that can't contain the target. After the quarter is eliminated do searches in the remaining matrix elements. At first it seemed to me that the complexity is O(log N*M), but it looks like I'm wrong. Can anyone show how to calculate complexity of this algorithm?

```
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix.length == 0) return false;
return search(matrix, target, 0, matrix.length-1, 0, matrix[0].length-1);
}
private boolean search(int[][]matrix, int target, int minRow, int maxRow, int minCol, int maxCol) {
if (minRow>maxRow || minCol>maxCol) return false;
int midRow = (minRow + maxRow) /2;
int midCol = (minCol + maxCol) /2;
int val = matrix[midRow][midCol];
if (val == target) return true;
if (target<val) {
return search(matrix, target, minRow, maxRow, minCol, midCol - 1) ||
search(matrix, target, minRow, midRow - 1, midCol, maxCol);
} else {
return search(matrix, target, midRow+1, maxRow, minCol, maxCol) ||
search(matrix, target, minRow, midRow, midCol+1, maxCol);
}
}
}
```