Share my C++ solution,time complexity is O(log m + log n)

• ``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
if (row == 0)
return false;
int col = matrix[0].size();
if (col == 0)
return false;

if (target < matrix[0][0] || target > matrix[row-1][col-1])
return false;

int left = 0, right = row * col - 1, mid = 0, value = 0;

while (left <= right)
{
mid = left + (right - left) / 2;
value = matrix[mid / col][mid % col];

if (target == value)
return true;
else if (target < value)
right = mid - 1;
else
left = mid + 1;
}

return false;
}
};
``````

or:

``````class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int row = matrix.size();
if (row == 0)
return false;
int col = matrix[0].size();
if (col == 0)
return false;

if (target < matrix[0][0] || target > matrix[row-1][col-1])
return false;

int l1 = 0, r1 = row - 1, mid1 = 0;
int l2 = 0, r2 = col - 1, mid2 = 0;

while (l1 <= r1)
{
mid1 = l1 + (r1 - l1) / 2;
if (target == matrix[mid1][0] || target == matrix[mid1][col-1])
return true;
if (target > matrix[mid1][0] && target < matrix[mid1][col-1])
{
l2 = 0, r2 = col - 1;

while (l2 <= r2)
{
mid2 = l2 + (r2 - l2) / 2;
if (target == matrix[mid1][mid2])
return true;
else if (target < matrix[mid1][mid2])
r2 = mid2 - 1;
else
l2 = mid2 + 1;
}

return false;
}

if (target < matrix[mid1][0])
r1 = mid1 - 1;
else if (target > matrix[mid1][col-1])
l1 = mid1 + 1;
}

return false;
}
};``````

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