# My O(log(m) + log(n)) solution - just a few lines

• ``````class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
if(!matrix.size() or !matrix[0].size() or target < matrix[0][0]) return false;
int m = matrix.size(), n = matrix[0].size(), l = 0, r = m * n, k;
while(l + 1 < r) {
k = (l + r) / 2;
if(matrix[k/n][k%n] <= target) l = k;
else r = k;
}
return matrix[l/n][l%n] == target;
}
};
``````

My idea is just treat the matrix as an flattened sorted array and do the binary search. The trick is you need to convert you 1D index to 2D index using devide&mod.

• if matrix is [[1,2]], target is 2, can you get the correct result?

• Yes, it can.

• Wouldn't this be log(mn) instead of log(m) + log(n) ?

• log(m) + log(n) = log(m * n)...

• This post is deleted!

• great idea ! simple solution !

• Will not work for input

[[1,2,3,4,5],[3,4,6,11,14],[5,7,9,12,15],[7,9,15,20,22],[9,12,16,25,29]]
11

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