74. 搜索二维矩阵（Search a 2D Matrix）

频次 ★★★ · 难度 🟡 · 高频：百度

题目

m×n 矩阵，每行从左到右升序，每行第一个元素 > 上一行最后一个（即按行展开后是一个递增数组），判断 target 是否存在。

示例：

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

思路

将二维映射为一维二分：矩阵整体有序，行展开就是升序数组。把 [0, m×n-1] 作为搜索区间，取 mid 后通过 row = mid / n、col = mid % n 映射回矩阵位置。

比”从右上角搜索”更优：本题满足”整体系递增”，可以直接 O(log(mn))。

代码

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    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(mn)) —— 一维二分
• 空间：O(1)

边界条件

• 空矩阵：m == 0 || n == 0，需要开头防御
• 单行单列（[[1]]）：正常二分
• target 比 matrix[0][0] 小或比最后一格大：二分自然返回 false

变式

• 240. 搜索二维矩阵 II：每行/列各自升序，但非全量递增（上一行末 ≤ 下一行首不保证）。此时二分不管用，用 Z 字形搜索（从右上角开始，行首≤t≤行末才进入行，否则跳过整行）或每行分别二分
• 先找行再找列：本题也能先二分确定行，再二分该行（两次二分），但一次二分更简洁

易错点

• 映射关系：mid / n 是行号，mid % n 是列号。不是 mid / m（那是按列展开），需要想清楚——建议在纸上画个 3×4 矩阵验证
• 行展开数组最大下标 m×n - 1，不是 m×n
• 本题条件”每行第一个 > 上一行最后一个”是一次二分的前提；若只有”每行升序”但不保证全量递增，就是 240 题，解法不同

面试追问

• 如果不保证每行首 > 上一行末（只保证每行升序），怎么做？ 对每一行做一次二分，O(m log n)，或从右上角 Z 字形搜 O(m+n)。先确认”题目条件是否给全量有序”再选解法
• 二维转一维映射的通用思路？ 只要二维索引 (r,c) 与一维索引 i = r*n + c 形成双射，任何只需顺序访问的场景（遍历、二分、前缀和）都能转换

关联题

• 同套路：4. 寻找两个正序数组的中位数 —— 二分在不同数据结构上的映射
• 进阶：240. 搜索二维矩阵 II —— 条件放宽后的 Z 字形解法
• 知识点：二分查找的”映射”思维