```
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int m = matrix.size();
int n = matrix[0].size();
if (m == 0 || n == 0)
return false;
int row_num; // 1 base
// search in matrix[i][0] to get row number
int low = 1;
int high = m;
while (low <= high)
{
int mid = (low + high) / 2;
if (target > matrix[mid-1][0])
{
low = mid + 1;
}
else if (target < matrix[mid-1][0])
{
high = mid - 1;
}
else
{
return true;
}
}
if (high < low)
{
if (high == 0)
{
return false;
}
if (low == m+1)
{
if (target > matrix[high-1][n-1])
return false;
}
row_num = high;
}
// search in row_num row
low = 1;
high = n;
while (low <= high)
{
int mid = (low + high) / 2;
if (matrix[row_num-1][mid-1] == target) {
return true;
}
else if (matrix[row_num-1][mid-1] < target) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
return false;
}
```

};