Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode 74. Search a 2D Matrix
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m = len(matrix)
if m == 0:
return False
n = len(matrix[0])
if n == 0:
return False
# find last num in first column that <= target
lo = 0
hi = m - 1
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if matrix[mid][0] <= target:
lo = mid
else:
hi = mid - 1
if matrix[lo][0] > target:
return False
row = lo
# find target in that row
lo = 0
hi = n - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if matrix[row][mid] == target:
return True
elif matrix[row][mid] < target:
lo = mid + 1
else:
hi = mid - 1
return False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment