Solution1:

Treat the matrix as a sorted list, and use binary search.

```
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target)
{
if(matrix.empty()) return false;
int height = matrix.size();
int width = matrix[0].size();
if(matrix[0][0] > target || matrix[height-1][width-1] < target) return false;
int head = 0,tail = height*width-1;
int mid,midRow,midCol;
while(head <= tail)
{
mid = (head+tail)/2;
midCol = mid%width;
midRow = mid/width;
if(matrix[midRow][midCol] < target)
head = mid+1;
else if(matrix[midRow][midCol] > target)
tail = mid-1;
else
return true;
}
return false;
}
};
```

Solution2:

Use binary search for matrix[i][0] to find the row where target is in, and then use binary search for matrix[row][j] to find target. This solution is better because it avoids multiplication overflow(height*width) and / and % while it's complexity is the same as solution1.

```
class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix,int target)
{
if(matrix.empty()) return false;
int heigth = matrix.size();
int width = matrix[0].size();
if(matrix[0][0] > target || matrix[heigth-1][width-1] < target) return false;
int head = 0;
int tail = heigth-1;
int mid;
while(head != tail && matrix[tail][0] > target)
{
mid = (head+tail+1)/2;
if(matrix[mid][0] < target) head = mid;
else if(matrix[mid][0] > target) tail = mid-1;
else return true;
}
int row = tail;
head = 0,tail = width-1;
while(head <= tail)
{
mid = (head+tail)/2;
if(matrix[row][mid] < target)
head = mid + 1;
else if(matrix[row][mid] > target)
tail = mid -1;
else return true;
}
return false;
}
};
```