# 6-12 lines, O(log(m) + log(n)), myself+library

• 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``````

• Why do we have to set hi = mid instead of hi = mid - 1 in your first solution? Thx.

• @dianhua1560 My `hi` is exclusive, so setting it to `mid - 1` would rule that out. But it shouldn't.

• got it. Thanks!

• Great job!!!

• Here is my 1-line python, hope that you like it:

``````def searchMatrix(self, matrix, target):
return bool(matrix) and target in matrix[bisect.bisect(matrix, [target + 0.5]) - 1]
``````

If you want to do `bisect` twice:

``````def searchMatrix(self, matrix, target):
m = bisect.bisect(matrix, [target+0.5])
return len(matrix[0]) > 0 and matrix[m - 1][bisect.bisect(matrix[m - 1], target) - 1] == target if m else False
``````

which equals to:

``````def searchMatrix(self, matrix, target):
m = bisect.bisect(matrix, [target + 0.5])
if m:
n = bisect.bisect(matrix[m - 1], target)
return len(matrix[0]) > 0 and matrix[m - 1][n - 1] == target
return False``````

• @lee215 I like the one-liner, though it has different complexity. In your other solutions I don't like the redefinition of m and n. The problem already defined them to be height and width of the matrix (as is the standard in math/compsci).

Slight variation:

``````def searchMatrix(self, matrix, target):
i = bisect.bisect(matrix, [target + 0.5]) - 1
return any(matrix) and matrix[i][bisect.bisect(matrix[i], target) - 1] == target``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.