# O(m*log(n)) solution in C++ - accepted.

• Very happy about that - looks like I can still remember to do some stuff right...

That being said, shout if you can see anything blatantly stupid. Thanks!

``````class Solution {
public:

bool searchRowBinary(vector<int>& a, int target, int start, int end) {
if (start==end)
{
if (a[start]==target)
return true;
else
return false;
}
else
{
int mid = (end+start)/2;
if(a[mid]>=target)
return searchRowBinary(a, target, start, mid);
else
return searchRowBinary(a, target, mid+1, end);
}
}

bool searchMatrix(vector<vector<int>>& matrix, int target) {
bool found = false;
for(int i = 0; i < matrix.size(); i++)
{
if (matrix[i][0] <= target)
{
found = searchRowBinary(matrix[i], target, 0, matrix[i].size()-1);
}
else
break;

if (found)
break;
}
return found;
}
};``````

• "shout if you can see anything blatantly stupid"

The title.

(Your solution isn't O(log(m*n)) but only O(m log n))

• True! Thanks for pointing out. I will try to amend the title.

• My code improves this algorithm.

The concept is to narrow the range each time we search a row.

For example, we have a matrix like:

1 5 9 10...

2 6 11 21 ...

4 7 20 30...

and the target is 6.

When searched the first line, your algorithm is going to search:

2 6 11 21 ...

4 7 20 30...

But in fact we only need to search, as 9 in the first row is larger than 6:

2 6

4 7

Because the right part is impossible.

In addition, I replace binary search with linear search when the range get small.

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