LC 0240 [M] Search a 2D Matrix II - ALawliet/algorithms GitHub Wiki
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int)-> bool:
ROWS, COLS = len(matrix), len(matrix[0])
if not ROWS or not COLS:
# Quick response for empty matrix
return False
for row in matrix:
# range check
if row[0] <= target <= row[-1]:
# launch binary search on current possible row
l, r = 0, COLS-1
while l <= r:
m = (l + r) // 2
if target == row[m]:
return True
elif target > row[m]:
l = m + 1
elif target < row[m]:
r = m - 1
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS, COLS = len(matrix), len(matrix[0])
r = len(matrix) - 1
c = 0
while 0 <= r < len(matrix) and 0 <= c < len(matrix[0]):
if matrix[r][c] == target:
return True
elif target > matrix[r][c]:
c += 1
else:
r -= 1
return False