LC74　搜索二维矩阵¶

中等通过率 52.7%python3核心代码模式二分查找样例通过牛客 AC数组二分查找矩阵

讲解章节：二分

一句话

两条性质让整个矩阵按行首尾相接就是一个升序序列，于是当成一维数组二分。

解题思路¶

这题考什么¶

题面给的两条性质要合起来读：

每行从左到右非严格递增；
每行的第一个数大于上一行的最后一个数。

第一条说每行内部有序，第二条说行与行之间也接得上。两条一起，把矩阵按行拼接成一条长度 m * n 的序列后，整条序列是升序的：

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]
拼接后   1 3 5 7 | 10 11 16 20 | 23 30 34 60

于是这题没有任何「二维」成分，就是在一个长度 m * n 的升序数组里查一个数。直接套二分四种写法里的写法三（闭区间 + 命中即返回），见二分的 44.2 节。

唯一要做的事是下标换算。把拼接后的位置 mid 还原回二维坐标：

行号 = mid // n     （n 是每行的列数；整除算出 mid 前面能填满几整行）
列号 = mid % n      （余数就是它在这一行里的偏移）

注意除数是列数 n，不是行数 m——一行装 n 个元素，所以「几个 n 为一行」。这两个式子是行优先（row-major）存储与一维下标之间的标准互换，与 C 语言里二维数组的内存布局是同一回事。

另一条常见解法是「两次二分」：先在每行的首元素上二分定位行，再在行内二分定位列，复杂度同样是 O(log m + log n) = O(log(m * n))，但要写两段二分、还要处理「目标比第一行首元素还小」的边界。拼成一维只写一段二分，更短也更难写错。

数据规模与复杂度¶

1 <= m, n <= 100，所以 m * n 至多 1e4；元素与 target 都在 [-1e4, 1e4]。时间 O(log(m * n))：区间长度至多 1e4，二分至多 14 轮。空间 O(1)。逐格扫描是 O(m * n) = 1e4 次比较，这个数据量下也不慢，但题面明确要求 O(log(m * n))，线性做法不满足要求。

坑在哪¶

换算用的除数必须是列数 n。写成 mid // m 与 mid % m，在 m == n 的方阵上照样全对，非方阵才露馅。拿样例那个 3 行 4 列的矩阵实测： target = 7 与 target = 20 会返回 False（这两个数明明在矩阵里）， target >= 35 的那些则直接 IndexError——因为 mid // m 最大到 11 // 3 = 3，已经超出只有 3 行的行号范围。这类下标偏移错误多数时候不报错，只会安静地给出错误答案，最难查。
n 取 len(matrix[0])，靠的是题面保证 1 <= n，即矩阵不含空行。若允许空行，len(matrix[0]) 会是 0，mid // n 直接除零。
用的是闭区间写法：right 初值 m * n - 1（最后一个合法位置），循环条件 while left <= right。两者必须成套用—— 闭区间配 left < right 会漏掉区间只剩一个元素的那一轮， matrix = [[1]]、target = 1 就会返回 False。
两个收缩分支都把 mid 本身踢出区间（left = mid + 1 / right = mid - 1），区间每轮至少缩短 1，因此不会死循环。命中在循环内直接返回，不必等区间收敛。
返回的是布尔值，不是下标。判题按结构严格比对，返回 0 / 1 或者下标都不对。
m * n 至多 1e4，left + right 不会溢出——Python 的整数本来就没有上界， C++ 里常写的 left + (right - left) // 2 在这里是多余的。

样例复核¶

matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]]，m = 3、n = 4，区间 [0, 11]。 target = 3：

mid = 5  -> matrix[5 // 4][5 % 4] = matrix[1][1] = 11 > 3，right = 4
mid = 2  -> matrix[0][2] = 5 > 3，right = 1
mid = 0  -> matrix[0][0] = 1 < 3，left = 1
mid = 1  -> matrix[0][1] = 3 命中，返回 True，与样例一致。

target = 13：区间依次收成 [0,11] -> [6,11] -> [6,7] -> [7,7] -> [8,7] 为空，

返回 False，与样例一致。

参考实现¶

solutions/leetcode/LC74/sol.py
from typing import List, Optional


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        m = len(matrix)
        # 列数。题面保证 n >= 1，矩阵没有空行，所以 matrix[0] 一定取得到，
        # 后面拿 n 当除数也不会除零
        n = len(matrix[0])
        # 把矩阵按行首尾相接看成一条长度 m * n 的升序序列，在它的下标上二分。
        # 搜索区间是**闭区间** [left, right]，两端都还没被检查过
        left = 0
        right = m * n - 1
        # 闭区间必须配 <=：left == right 时区间还剩一个元素，那一格仍要检查。
        # 写成 < 会漏掉它，1 行 1 列的矩阵直接答错
        while left <= right:
            mid = (left + right) // 2
            # 一维下标还原成二维坐标：一行装 n 个元素，所以整除 n 得行号、模 n 得列号。
            # 除数是**列数 n** 而不是行数 m，在方阵上写错也看不出来，非方阵立刻错位
            value = matrix[mid // n][mid % n]
            if value == target:
                # 命中即返回，不必等区间收敛
                return True
            if value < target:
                # 拼接后的序列升序，mid 及其左边全部 < target，整段排除
                left = mid + 1
            else:
                # value > target，mid 及其右边全部 > target，整段排除。
                # 两支都把 mid 踢出区间，区间每轮至少缩短 1，不会死循环
                right = mid - 1
        # 因 left > right（区间为空）退出，说明整条序列里没有 target
        return False

LC74 搜索二维矩阵¶