# Java solution in log4/3(N*M);

• ``````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;
}
``````

}

• Hi Amisarca,

Thank you for sharing your solution!

I had the same idea as yours at the beginning, but in my understanding, the time complexity is (by master theorem):

``````T(n) = 3 * T(0/75 * n) + O(1)  ==> O(n ^ log(3, 1.33)) = O (n ^ 3.82)
``````

where 0.75 is a rough guess but I think is a good estimation (actually 0.75 is the best case).

So this is not binary search (a = 3 not 1) and it indeed has an unideal time complexity; the top-right to bottom-left search solution is much better.

Zijiao

• Your analysis suggests this algorithm is even worse than the brute force one?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.