```
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.