74. Search a 2D Matrix

──────────────────────────────────────────────────────────────────────

在一個矩陣裡找 target。矩陣的性質是：每一列由左到右遞增，而且每一列的第一個數字都大於上一列的最後一個數字。

思路

題目那兩個條件加起來其實在說一件事：

把整個矩陣一列一列接起來，就是一個完全排序的一維陣列。

一旦看穿這點，題目就從「二維搜尋」變回「在排序陣列上二分搜尋」—— 一個已經會的問題。剩下的只是索引換算。

這是這題最重要的一步：先問「這個資料結構等價於什麼我已經會的東西」，而不是急著設計二維的搜尋策略。

索引怎麼換算

把一維索引 idx 對應回二維座標，用 cols（每列的長度）做除法和取餘：

row = idx // cols —— 走過幾個完整的列
col = idx % cols —— 在那一列的第幾個

反過來 idx = row * cols + col。這組換算在很多「把二維攤平成一維」的題目都會用到。

注意除數是 cols 不是 rows，這是最容易寫反的地方 —— 想成「每前進 cols 個元素就換一列」就不會錯。

解題方向

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        cols = len(matrix[0])

        def getVal(idx):
            row = idx // cols
            col = idx % cols
            return matrix[row][col]
        left = 0
        right = rows * cols - 1

        while left <= right:
            mid = left + (right - left) // 2
            if getVal(mid) == target:
                return True
            elif getVal(mid) > target:
                right = mid - 1
            elif getVal(mid) < target:
                left = mid + 1
        
        return False

把換算包成 getVal 是很好的做法：二分搜尋的邏輯完全沒被二維的細節污染，跟一維版本長得一模一樣。面試時這樣寫也比較好解釋 —— 先說「我把它當成長度 rows * cols 的排序陣列」，再說「getVal 負責把索引翻譯回座標」。

用的是左閉右閉區間（right = n - 1、while left <= right、right = mid - 1），三個地方要一致。邊界寫法固定一種練到閉著眼睛都不會錯，見 Binary Search 模板。

mid = left + (right - left) // 2 而不是 (left + right) // 2 是為了避免整數溢位 —— Python 的整數無上限所以不影響，但在 Java / C++ 是必要的，寫成這樣是好習慣。

補充

別和 240. Search a 2D Matrix II 搞混。 兩題長得很像但條件不同，導致解法完全不同：

	矩陣性質	能不能攤平成一維	解法	複雜度
74 這題	每列遞增，且下一列的開頭 > 上一列的結尾	可以	一次二分	$O (\log (m n))$
240	每列遞增、每行遞增，但列與列之間沒有保證	不行	從右上角往左下走	$O (m + n)$

240 之所以不能攤平，是因為 [[1,4],[2,5]] 這種矩陣攤平成 [1,4,2,5] 並不是排序的。讀題時要特別確認是哪一種，這是這兩題最常見的混淆點。

240 的解法也很漂亮：從右上角出發，比 target 大就往左（整行排除）、比 target 小就往下（整列排除），每一步都能刪掉一整行或一整列。

其他二分搜尋題：704. Binary Search（最基本的模板）、35. Search Insert Position、33. Search in Rotated Sorted Array（旋轉過的陣列）。

複雜度

時間 $O (\log (m n))$ — 對長度 m × n 的虛擬一維陣列做二分；也可以寫成 $O (\log m + \log n)$ ，兩者相等
空間 $O (1)$ — 只有幾個索引變數，沒有真的把矩陣攤平成新陣列

其中 m、n 是矩陣的列數和行數。

「沒有真的攤平」值得強調：getVal 是即時換算的，所以空間是 $O (1)$ 。如果真的建一個一維陣列就會變成 $O (m n)$ 。