LeetCode 獨自升級紀 - [Binary Search] Search a 2D Matrix (Medium)

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

for i in range(len(matrix)):
    for c in matrix[i]:
        if c == target:
            return True
return False