LeetCode 搜索二維矩陣 I：將矩陣視為一維有序數組二分查找

題目描述

給定一個 m x n 矩陣，滿足：

• 每行從左到右遞增
• 下一行第一個元素大於上一行最後一個元素

判斷目標值是否存在於矩陣中。

範例：

matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3 → true
target = 13 → false

解題思路：一維索引映射二維座標

矩陣整體可視為長度 m*n 的有序數組。二分查找中，將一維索引 mid 映射為二維座標：

row = mid // n
col = mid % n

時間複雜度：O(log(mn))，空間複雜度：O(1)。

Python 參考實現

class Solution:
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix or not matrix[0]:
            return False
        
        m, n = len(matrix), len(matrix[0])
        left, right = 0, m * n - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            row, col = divmod(mid, n)
            val = matrix[row][col]
            
            if val == target:
                return True
            elif val < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

# 測試
if __name__ == "__main__":
    sol = Solution()
    assert sol.searchMatrix([[1,2,3],[4,5,6],[7,8,9]], 5) == True
    assert sol.searchMatrix([[1,2],[3,4]], 4) == True
    assert sol.searchMatrix([[1]], 2) == False
    print("所有測試通過")

核心要點總結

• 矩陣性質利用：行間遞增 + 行首 > 上行尾 → 全局有序
• 索引映射公式：row = mid // n, col = mid % n 或 divmod(mid, n)
• 邊界處理：空矩陣、單元素矩陣均正確處理
• 對比題目：LeetCode 240 (Search a 2D Matrix II) 只有行列各自有序，需右上角/左下角搜索法

這道題展示了「降維思維」：將二維問題映射為一維問題，復用經典二分查找模板。