# C++ 12ms Solution using Binary Search [O(log(m) + log(n))]

• ``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size(), x, y;
int lo = 0, hi = m*n-1, mid;
if (hi == 0) return (matrix[0][0] == target);
while (lo <= hi)
{
mid = lo + (hi-lo)/2;
x = mid / n; y = mid % n;
if (matrix[x][y] == target)
return true;
else if (matrix[x][y] > target)
hi = mid-1;
else
lo = mid+1;
}
return false;
}
};``````

• My solution also use Binary Search, where the boundary values are also checked within one loop.

``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int start = 0;
int end = matrix.size();
if(end == 0) return false;
int len = matrix[0].size();
end = end * len - 1;

int mid;
while(start <= end){
mid = (start + end)/2;

int i = start / len;
int j = start % len;
if(matrix[i][j] > target) return false;
if(matrix[i][j] == target) return true;

i = end / len;
j = end % len;
if(matrix[i][j] < target) return false;
if(matrix[i][j] == target) return true;

i = mid / len;
j = mid % len;
if(matrix[i][j] == target) return true;
if(matrix[i][j] < target) {
start = mid + 1;
end --;
} else {
start++;
end = mid - 1;
}
}

return false;

}
};
``````

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