bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size();
if (m == 0) return false;
int n = matrix[0].size();
int i = 0, j = n  1;
while (i < m && j >= 0) {
if (matrix[i][j] == target)
return true;
else if (matrix[i][j] > target) {
j;
} else
i++;
}
return false;
}
C++ with O(m+n) complexity


I think my solution is log(m)+log(n). Divide the matrix into 4 part, when the middle point is less than target, discard the bottom right part, otherwise if it is greater than target, discard the top left part.
public class Solution { public boolean searchMatrix(int[][] matrix, int target) { int n=matrix.length, m=matrix[0].length; return helper(matrix,0,n1,0,m1,target); } boolean helper(int[][] matrix, int rowStart, int rowEnd, int colStart, int colEnd, int target ){ if(rowStart>rowEndcolStart>colEnd){ return false; } int rm=(rowStart+rowEnd)/2, cm=(colStart+colEnd)/2; if(matrix[rm][cm]== target){ return true; } else if(matrix[rm][cm] >target){ return helper(matrix, rowStart, rm1,colStart, cm1,target) helper(matrix, rm, rowEnd, colStart,cm1,target)  helper(matrix, rowStart, rm1,cm, colEnd,target); } else{ return helper(matrix, rm+1, rowEnd, cm+1,colEnd,target) helper(matrix, rm+1, rowEnd, colStart,cm,target)  helper(matrix, rowStart, rm,cm+1, colEnd,target); } }
}

Your divideandconquer solution is dividing the matrix into 4 quadrants and searching in 3 of the quadrants in each recursion. Its runtime complexity can not be log(m) + log(n).
I have wrote an article which derives the runtime complexity with the restriction of
m = n
. Basically you have to solve the recurrence relation:T(n) = 3T(n/2) + c
, which gives the final complexity around: O(n^{1.58})

class Solution { public: int target; bool searchMatrix(vector<vector<int> >& matrix, int target) { this>target = target; int n = matrix.size()1, m = matrix[0].size()1; return Find(matrix,0,0,n,m); } bool Find(vector<vector<int> > &matrix, int i,int j,int n, int m) { if(i>n  j>m) return false; int midX = (i+n)>>1, midY = (j+m)>>1; if(matrix[midX][midY] == target) return true; else if(matrix[midX][midY] > target) { return Find(matrix,i,j,midX1,midY1)  Find(matrix,i,midY,midX1,m)  Find(matrix,midX,j,n,midY1); } else return Find(matrix,i,midY+1,midX,m)  Find(matrix,midX+1,j,n,midY)  Find(matrix,midX+1,midY+1,n,m); } };
The same code with c++ , get TLE, WHY ??

Hi, 1337c0d3r
If you still remember the following discussion:November 12, 2010 at 11:25 am You are welcome. BTW, just noticed another thing: O(nlgn) is actually better than O(n^1.58) 0 Reply ↓ 1337c0d3r November 14, 2010 at 5:28 pm You made a very great observation! I need to investigate my code running time why it doesn't reflect this. One speculation is in the quad partition, I use an extra condition if (l > r  u > d) return false; to bail out early, while my binary search code does not use this. I will update my findings. Thanks! 0 Reply ↓ 1337c0d3r November 15, 2010 at 12:34 pm Just to post a followup regarding aNiceGuy's observation that O(n lg n) has a lower bound than O(n^1.58), which is true. The two algorithms (binary search and diagonal binary search) which runs in O(n lg n), runs in a significant longer time than the quad partition method (O(n^1.58). One way to explain this is that both binary search and diagonal binary search has a higher constant than the quad partition. Also due to N=1000 is not large enough, therefore n^1.58 has not overtake n lg n yet. But if N is large enough, eventually n^1.58 will rise exponentially while n lg n remain pretty flat.
It seems that, quad partition is really faster than n times 1D binary search...So, N^1.58 may not be correct... if applying T(n)=3T(n/4)+c,thinks may be different. Thanks

I think @sydy71 is correct. There are 3 recursive calls, and each call reduce the problem size to 1/4 of the original problem.
So T(N) <= 3T(N/4) + O(1). Using master theorem, the time complexity is O(N^(log(4,3)), which is approximately O(N^0.79), where N is the total number of elements in the matrix, which is m*n

@sydy71: It depends what you meant by n. Here, we assume
m = n
(the matrix is a square), and n is the length of the square matrix's side. So, T(n) = 3T(n/2) + c.


You can firstly do a binary search on diagonal and find two neighboring elements which are less and greater than target. You can thus get rid of the topleft and bottomright submatrix. You then only need to search in the topright and bottom left submatrices. So, n=max(M,N), T(n)=2T(n/2)+log(n), complexity is O(n).

beats 98%
'''bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(); if(m<1) return false; int n = matrix[0].size(); if(n<1) return false; int i=0; while(i<m && target >= matrix[i][0]) { int low = 0; int high = n; while(low < high) { int mid = (low+high)/2; if(matrix[i][mid] > target) high = mid; else if(matrix[i][mid] < target) low = mid+1; else return true; } ++i; } return false; }
'''