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