O(logm+logn) solution (AC) using C++

• class Solution {
public:
bool search(vector<vector<int>> &matrix,int si,int ei,int sj,int ej,int target){

``````    if(si>ei||sj>ej
||matrix[si][sj]>target
||matrix[ei][ej]<target)
return false;
//si is up side,ei is down side,sj is left side, ej is right side
int mi=(si+ei)/2;
int mj=(sj+ej)/2;

if(matrix[mi][mj]==target)
return true;
else if(matrix[mi][mj]<target){
return search(matrix,si,mi,mj+1,ej,target)
||search(matrix,mi+1,ei,sj,mj,target)
||search(matrix,mi+1,ei,mj+1,ej,target);
}else{
return search(matrix,si,mi-1,mj,ej,target)
||search(matrix,mi,ei,sj,mj-1,target)
||search(matrix,si,mi-1,sj,mj-1,target);
}
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if(matrix.empty()) return false;

return search(matrix,0,matrix.size()-1,0,matrix[0].size()-1,target);
}
``````

};

• That's not O(logm+logn) (or not correct).

• you are right, it's a quite heavy algorithm indeed. But it works indeed.

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