I have two solutions, one without and one with using the library. Both have runtime O(log(m) + log(n)), or in other words, O(log(mn)).

**Solution 1: One Binary Search** (48 ms, 12 lines)

Here I treat the matrix like a single big list of length m*n and use a simple binary search. I only have to convert the list indexes to matrix indexes on the fly.

```
def searchMatrix(self, matrix, target):
n = len(matrix[0])
lo, hi = 0, len(matrix) * n
while lo < hi:
mid = (lo + hi) / 2
x = matrix[mid/n][mid%n]
if x < target:
lo = mid + 1
elif x > target:
hi = mid
else:
return True
return False
```

**Solution 2: Using the library** (48 ms, 6 lines)

If there were a library function doing the 2D search, it would be boring, but there isn't. So it's still a little challenge to figure out how to use the 1D functions that *are* there. Here I use `bisect`

to (approximately) find the candidate row and then `bisect_left`

to find the candidate cell in that row.

```
def searchMatrix(self, matrix, target):
i = bisect.bisect(matrix, [target])
if i < len(matrix) and matrix[i][0] == target:
return True
row = matrix[i-1]
j = bisect.bisect_left(row, target)
return j < len(row) and row[j] == target
```