74. 搜索二维矩阵

LeetCode 74¹ · 中等 · 二分查找

题

给一个 \(m \times n\) 整数矩阵：每行从左到右非降序，且每行第一个数大于上一行最后一个数。判断 target 是否在矩阵里。

例：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3 → true；target = 13 → false。

一句话

两条性质合起来说明按行读出来整体升序——把矩阵当成长 \(mn\) 的虚拟数组，第 \(k\) 个元素是 matrix[k // n][k % n]，直接二分。

关键技巧

识别「虚拟有序数组」。 「行内有序」+「下一行首 > 上一行尾」\(\iff\) 行优先展开后全局有序。不需要真的拉平（那是 \(O(mn)\)），只需要下标映射：

二分模板不变：左闭右开 \([lo, hi)\) 找第一个 >= target 的位置 lo，最后检查 lo < mn 且那个位置等于 target。不变量与 35. 搜索插入位置 完全一致。

另一种写法：先二分找「最后一个行首 <= target」的行，再在该行内二分——两次 \(O(\log m) + O(\log n)\)，总量一样是 \(O(\log mn)\)，代码多一截，好处是不做除法。

解

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        lo, hi = 0, m * n  # 虚拟数组上的 [lo, hi)
        while lo < hi:
            mid = (lo + hi) // 2
            if matrix[mid // n][mid % n] >= target:
                hi = mid
            else:
                lo = mid + 1
        return lo < m * n and matrix[lo // n][lo % n] == target

时间 \(O(\log mn)\)，空间 \(O(1)\)。

延伸

• 只有行有序、列有序，没有首尾相接：拉不平，二分失效。改用从右上角出发的「阶梯走法」，每步排除一行或一列，\(O(m+n)\)——见 240. 搜索二维矩阵 II。本题当然也能用阶梯法，但浪费了更强的条件。
• 二维下标与一维下标的互换在 54. 螺旋矩阵、48. 旋转图像 这类矩阵题里也常用。

s = Solution()
M = [[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]]
assert s.searchMatrix(M, 3) is True
assert s.searchMatrix(M, 13) is False
assert s.searchMatrix(M, 60) is True and s.searchMatrix(M, 61) is False
assert s.searchMatrix(M, 0) is False
assert s.searchMatrix([[1]], 1) is True