搜索二维矩阵 | 每日算法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你一个满足下述两条属性的 m × n 整数矩阵：

每行中的整数从左到右按非严格递增顺序排列。
每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target，如果 target 在矩阵中，返回 true；否则，返回 false。

你必须编写一个时间复杂度为 O(log(m × n)) 的解决方案。

示例 1

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3

输出：true

示例 2

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13

输出：false

💭 模拟答题者思考

1. 暴力：逐格扫描整个矩阵，O(m×n)——能判断是否存在，但题目要求 O(log(m×n))。

2. 重复在哪里？题目保证「行内升序」且「下一行首元素 > 上一行末元素」，所以若按行从左到右、从上到下依次读，得到的是一条完整升序序列，与把矩阵拉平成一维数组等价。

3. 关键转化：在虚拟一维下标 [0, m×n-1] 上写普通二分；下标 mid 对应元素为 matrix[mid // n][mid % n]，无需真的复制数组。

4. 例 target = 3：拉平后序列以 1,3,5,7,10,... 开头，二分很快落在下标 1 的 3 上，返回 true；target = 13 落在 11 与 16 之间，区间收缩为空，返回 false。

5. 每轮排除一半下标，共 O(log(m×n)) 次比较；只用几个整型变量，空间 O(1)。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`l, r`	int	定义：把矩阵看成一维有序数组后，当前二分区间的左右下标，范围 `[0, m×n-1]` 维护：若 `target` 存在，其在一维下标必落在 `[l, r]` 内更新：每轮与 `mid` 处元素比较后，排除左半或右半
`mid`	int	定义：当前一维下标 `(l + r) // 2` 维护：对应矩阵元素 `matrix[mid // n][mid % n]` 处于当前搜索区间正中更新：每轮重新计算；若等于 `target` 直接返回 `true`
`row, col`	int	定义：`row = mid // n`、`col = mid % n`，将一维下标映射回二维坐标维护：按行优先展开时，下标 `0..n-1` 为第一行，`n..2n-1` 为第二行，依此类推更新：仅由当前 `mid` 与列数 `n` 推导，每轮随 `mid` 变化

⌨️ 落码步骤

1. 若矩阵为空，返回 false；令 m = len(matrix)、n = len(matrix[0])

2. 初始化 l = 0、r = m * n - 1

3. 当 l <= r：取 mid = (l + r) // 2，val = matrix[mid // n][mid % n]

4. 若 val == target 返回 true；若 val < target 则 l = mid + 1，否则 r = mid - 1

5. 循环结束返回 false

💻 代码实现

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        m, n = len(matrix), len(matrix[0])
        l, r = 0, m * n - 1
        while l <= r:
            mid = (l + r) // 2
            val = matrix[mid // n][mid % n]
            if val == target:
                return True
            if val < target:
                l = mid + 1
            else:
                r = mid - 1
        return False

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;
        int m = (int)matrix.size(), n = (int)matrix[0].size();
        int l = 0, r = m * n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            int val = matrix[mid / n][mid % n];
            if (val == target) return true;
            if (val < target)
                l = mid + 1;
            else
                r = mid - 1;
        }
        return false;
    }
};
// 时间 O(log(m×n))，空间 O(1)

📈 复杂度分析

时间复杂度 O(log(m × n))

空间复杂度 O(1)

⚠️ 常见坑

❗ 下标映射必须用 mid // n 与 mid % n（列数为 n）；误写成 mid // m 会访问错误格子。

❗ 本题矩阵性质是「全局升序拉平」，不能照搬搜索二维矩阵 II 的从右上角「走楼梯」做法当作 log 解；II 题只要求 O(m+n)。

❗ 空矩阵或 matrix[0] 为空时要先判断，否则 m * n - 1 或取列数会出错。

🔍 必测边界 Case

Case 1：1×1 且命中

matrix = [[5]], target = 5 → true

Case 2：1×1 未命中

matrix = [[5]], target = 3 → false

Case 3：target 小于最小值

matrix = [[1,3],[10,11]], target = 0 → false

Case 4：target 在最后一格

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