Solution with O(logM + logN)

• ``````class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();

//binary search rows
int low = 0, mid=0, row = -1;
int high = m - 1;
while(low <= high)
{
mid = (high+low)/2;
if (matrix[mid][0] <= target)
{
if(matrix[mid][n-1]>= target)	//find the row
{
row = mid;
break;
}
else
low = mid+1;
}
else
high = mid - 1;
}

if(row == -1)
return false;
//binary search column value
low = 0; high = n-1;
while (low<=high)
{
mid = (high + low)/2;
if (matrix[row][mid] == target)
return true;
else if (matrix[row][mid] < target)
low = mid+1;
else
high = mid-1;
}
return false;
}
};``````

• ``````// C++11 lambda and auto test
class Solution
{
public:
bool searchMatrix(vector<vector<int> > &matrix, int target)
{
auto it = upper_bound(matrix.begin(), matrix.end(), target,
[](int x, const vector<int> &a) { return x < a[0];});
if (it == matrix.begin()) return false;
it--;
auto jt = equal_range(it->begin(), it->end(), target);
if (jt.first == jt.second) return false;
else return true;
}
};``````

• I think this method is tuned to be wrong, for you can't decide which row may the value would be. For example, the [1, 3, 5, 13][10, 11, 16, 20][23, 30, 34, 50] and try to find target 13, this algorithm tune to get the answer.

• @tornador92 The first integer of each row is greater than the last integer of the previous row.

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