# Easy understand O(log(m)+log(n)) solution

• Every time I choose the center num of matrix, and compare it with target, if mid > target, target cannot be in downright, recursively search the other three part vice versa. f(mn) = 3f(mn/4) + 1, so the time complexity should be O(log(m)+log(n)). But my runtime only beat 2.91% of java submission. Is there anything wrong with my code?

``````public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
return searchMatrix(matrix, target, 0, matrix.length-1, 0, matrix[0].length-1);
}
//i1, i2, j1, j2 to denote search area
boolean searchMatrix(int[][] matrix, int target, int i1, int i2, int j1, int j2) {
if(i1 > i2 || j1 > j2 || i1 < 0 || j1 < 0 || i2 >= matrix.length || j2 >= matrix[0].length) return false;
int im = (i1 + i2)/2, jm = (j1 + j2)/2;
int mid = matrix[im][jm];
if(mid == target) return true;
// if mid > target, target cannot be in downright
// then search upleft, upright, downleft 左上，右上，左下
else if(mid > target) return searchMatrix(matrix, target, i1, im, j1, jm-1) || searchMatrix(matrix, target, i1, im-1, jm, j2) || searchMatrix(matrix, target, im+1, i2, j1, jm-1);
// 右上，左下，右下
else return searchMatrix(matrix, target, i1, im, jm+1, j2) || searchMatrix(matrix, target, im+1, i2, j1, jm) || searchMatrix(matrix, target, im+1, i2, jm+1, j2);
}
}
``````

• Hi,

If you could divide the left into two parts, not three parts, then that will reduce function call. As a result, it will speed up. So the main drawback for this recursive method is the function call and stack overhead. I don't know if it can be changed to iterative method. I guess not.

• good suggestion, but I haven't think up a two parts divide solution.

• Just merge the adjacent parts into one. Like up-left and up-right can be merged into one part. And down-left is another part.

• cool, I'll try.

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