# C++ Solution, 139ms, with explanation

• The idea here is to narrow down the matrix to get a sub-matrix indicated by [rbegin:rend][cbegin:cend].
For the beginning row, if its largest value (i.e., at end of the row) is less than the target, make the rbegin++, if its largest value is larger than the target, make the cend--.
For the last row, if the smallest value larger (i.e., at the beginning of the row) than the target, make the rend--, if its value smaller than the target, make the cbegin++.

After every iteration, the sub-matrix will become smaller and smaller.

``````    bool searchMatrix(vector<vector<int>>& matrix, int target) {

int rbegin=0, cbegin=0, rend=matrix.size()-1, cend=matrix[0].size()-1;
if(rend<0 || cend<0 || target<matrix[0][0] || target>matrix[rend][cend]) return false;
while(rbegin<=rend && cbegin<=cend){
int tmp=matrix[rbegin][cend];
if(tmp<target) rbegin++;
else if(tmp>target) cend--;
else return true;

tmp=matrix[rend][cbegin];
if(tmp>target) rend--;
else if(tmp<target) cbegin++;
else return true;

if(rbegin>rend || cbegin>cend) return false;
}
return matrix[rbegin][cbegin]==target;
}
``````

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