The restrictions on the matrix clearly show the intention for us to search in a linear space.

They always say interviewers like to see you break out subroutines where it makes sense and helps keeps things clear. I used a subroutine to do the lookup by translating the linear index into (row,col). Main routine then does does simple binary search. 12ms runtime.

```
class Solution {
public:
int getValue( vector<vector<int>>& matrix, int idx ) {
int rowSize = matrix[0].size();
int r = idx / rowSize;
int c = idx % rowSize;
return matrix[r][c];
}
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty()) return false;
if (matrix[0].empty()) return false;
int lo = 0;
int hi = matrix[0].size() * matrix.size() - 1;
while( lo < hi ) {
int mid = (lo+hi)/2;
int val = getValue(matrix,mid);
if (val < target) lo = mid+1;
else if (val > target) hi = mid;
else return true;
}
return ( getValue(matrix,lo) == target );
}
};
```