```
public bool SearchMatrix(int[,] matrix, int target) {
int row = FindRow(matrix,target);
if (row == -1)
return false;
int l = 0, r = matrix.GetLength(1) - 1;
int mid;
while(r >= l) {
mid = (r - l) / 2 + l;
if (target == matrix[row, mid])
return true;
else if (target < matrix[row, mid])
r = mid - 1;
else if (target > matrix[row, mid])
l = mid + 1;
}
return false;
}
private int FindRow(int[,] matrix, int target) {
int l = 0, r = matrix.GetLength(0) - 1;
int mid;
while (r >= l) {
mid = (r - l) / 2 + l;
if (target >= matrix[mid,0] && target <= matrix[mid,matrix.GetLength(1) - 1])
return mid;
else if (target < matrix[mid,0])
r = mid - 1;
else if (target > matrix[mid, matrix.GetLength(1) - 1])
l = mid + 1;
}
return -1;
}
```

The basic idea is next: firstly with a binary search find a row which could contain

the target (row[0] <= target and row[lenght - 1] >= target) and search in this row for our target.