LC 0074 [M] Search a 2D Matrix - ALawliet/algorithms GitHub Wiki
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int):
ROWS = len(matrix)
COLS = len(matrix[0])
lo = 0
hi = ROWS*COLS - 1
while lo <= hi:
m = (lo + hi) // 2
# r = m // COLS
# c = m % COLS
r, c = divmod(m, COLS)
if target == matrix[r][c]:
return True
elif target > matrix[r][c]:
lo = m + 1
elif target < matrix[r][c]:
hi = m - 1
return False
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
r = bisect_left(matrix, target, key=lambda row: row[-1]) # or key=itemgetter(-1) search for row
if r >= len(matrix): return False
c = bisect_left(matrix[r], target) # search for column
return matrix[r][c] == target
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
r = bisect_left(matrix, target, key=lambda row: row[-1]) # or key=itemgetter(-1) search for row
return r < len(matrix) and matrix[r][bisect_left(matrix[r], target)] == target # search for column
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS = len(matrix)
COLS = len(matrix[0])
def get(idx):
r, c = divmod(idx, COLS)
return matrix[r][c]
return get(bisect_left(range(ROWS*COLS-1), target, key=get)) == target
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
ROWS, COLS = len(matrix), len(matrix[0])
# binary search to find the row
top, bot = 0, ROWS - 1
while top <= bot:
row = (top + bot) // 2 # middle row
if target > matrix[row][-1]:
top = row + 1
elif target < matrix[row][0]:
bot = row - 1
else:
break
if not (top <= bot):
return False
# binary search within the row
row = (top + bot) // 2
l, r = 0, COLS - 1
while l <= r:
m = (l + r) // 2
if target > matrix[row][m]:
l = m + 1
elif target < matrix[row][m]:
r = m - 1
else:
return True
return False
# O(log(m*n))