Well, this matrix is super ordered, and it's very easy to find the **exact right** row, and then we can use binary search to search that **row**, instead of search the whole matrix.

*Just to be clear: this solution is definitely faster than 1-D solution.*

Two binary search, beat 70% in Java, code below:

```
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int m = matrix.length, n = matrix[0].length;
int top = 0, down = m - 1;
// find the row
while (top < down) {
int mid = top + (down - top) / 2;
if (matrix[mid][n - 1] >= target) {
down = mid;
} else {
top = mid + 1;
}
}
int row = top;
// find the value
int l = 0, r = n-1;
while (l < r) {
int mid = l + (r - l) / 2;
if (matrix[row][mid] >= target) {
r = mid;
} else if (matrix[row][mid] < target) {
l = mid + 1;
}
}
return matrix[row][l] == target;
}
```