m:=#rows, n:=#cols

**O(m+n)** time sol: use the upper-right corner and compare to target, if corner==target return true, else if corner > target 'delete' last col, if corner < target, 'delete' first row. Continue after you hit the lower-left corner.

```
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()) return false;
int i=0, j=matrix[0].size()-1;
while(i<matrix.size() && j>=0) {
if(matrix[i][j]==target) return true;
else if(matrix[i][j]<target) i++;
else j--;
}
return false;
}
```

**O(mlgn)** time sol. Loop over each row of the matrix, do binary search on each row. (no code)

**O(nlgm)** time sol. Loop over each col of the matrix, do binary search on each col. (since the data structure is 2D array, it is doable) (no code)

**O(logm + logn)** time sol is impossible. I made a mistake in claiming the following solution is O(logm + logn). But actually the time should be T(m,n) = T(m/2,n) + T(m/2,n/2) + c, which is **not** O(logm + logn)

```
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()) return false;
return search(matrix,target,0,matrix.size()-1,0,matrix[0].size()-1);
}
bool search(const vector<vector<int>>& matrix, int target, int m0, int m1, int n0, int n1) const {
if(m0>m1 || n0>n1) return false;
int i=m0+(m1-m0)/2, j=n0+(n1-n0)/2;
if(matrix[i][j]==target)
return true;
else if(matrix[i][j]<target)
return search(matrix,target,m0,m1,j+1,n1) || search(matrix,target,i+1,m1,n0,j);
else
return search(matrix,target,m0,i-1,n0,n1) || search(matrix,target,i,m1,n0,j-1);
}
```