32 lines
824 B
Python
32 lines
824 B
Python
def search_matrix(matrix, target):
|
|
if not matrix or not matrix[0]:
|
|
return False
|
|
top, bot = 0, len(matrix) - 1
|
|
while top <= bot:
|
|
mid = (top + bot) // 2
|
|
if matrix[mid][0] <= target <= matrix[mid][-1]:
|
|
row = mid
|
|
break
|
|
if target < matrix[mid][0]:
|
|
bot = mid - 1
|
|
else:
|
|
top = mid + 1
|
|
else:
|
|
return False
|
|
l, r = 0, len(matrix[row]) - 1
|
|
while l <= r:
|
|
m = (l + r) // 2
|
|
if matrix[row][m] == target:
|
|
return True
|
|
if matrix[row][m] < target:
|
|
l = m + 1
|
|
else:
|
|
r = m - 1
|
|
return False
|
|
|
|
|
|
if __name__ == "__main__":
|
|
matrix = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
|
|
print(search_matrix(matrix, 3))
|
|
print(search_matrix(matrix, 13))
|