# 題目
Example:
- Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
- Output: true
# Binary Search
class Solution:
def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
# double Binary Search
# matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
# 先從 rows 開始找
rows = len(matrix)
top, down = 0, rows - 1 # rows 的頭尾
while top <= down:
middle_row = (top + down) // 2
if (
target > matrix[middle_row][-1]
): # ，# 如果 target比mid的最右邊最大數字還要大，代表要往下，繼續去更大的 rows 中找
top = middle_row + 1
elif target < matrix[middle_row][0]: # 比這個 rows 的最小數字還要小
down = middle_row - 1
else:
break # 找到了 數字就在現在的 matrix[middle_row]
if not (top <= down):
# 代表 target 在矩陣的範圍外，直接回傳 False
# 為何還要判斷 if not (top <= bot)，不直接 return False？如果沒有這個判斷，程式會繼續往下跑
# 可能誤用 row 變數做第二次在 cols 中找，因為這時候根本沒有任何合法的 row 可以搜尋。
return False
l, r = 0, len(matrix[0]) - 1 # matrix[0] = cols 的長度 [[1,3,5,7],[...]]
while l <= r:
mid = (l + r) // 2
if target > matrix[middle_row][mid]: # 要更大，左邊的不要
l = mid + 1
elif target < matrix[middle_row][mid]: # 要更小，右邊的不要
r = mid - 1
else:
return True
return False時間與空間複雜度：
- TC：O(log(m * n))
- SC：O(1)
# Brute Force
for i in range(len(matrix)):
for c in matrix[i]:
if c == target:
return True
return False時間與空間複雜度：
- TC：O(m * n)
- SC：O(1)
