LeetCode 74. 搜索二维矩阵

约 4 分钟
文章信息 19 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 20-50 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 华为 微软 美团 拼多多 小米 百度 快手 猿辅导
标签
数组 二分查找 矩阵

题目描述

✅ 74. 搜索二维矩阵

image-20260928200311881

image-20260928200311882

题意分析

在一个非空矩阵中判断目标值是否存在。每一行从左到右非递减，且下一行的第一个元素严格大于上一行的最后一个元素，因此上一行的所有值都小于下一行的所有值。

两条条件合在一起，意味着按行依次读取整个矩阵，就得到一个有序数组。题目要求对数时间，可以直接对这份“虚拟数组”进行二分，而不必真的复制矩阵元素。

解法：虚拟一维数组二分查找

核心思路

[!blue]

设矩阵有 m 行、n 列，一共 m * n 个位置。按行编号后，一维下标 p 前面有 p / n 个完整行，因此它所在的行是 p / n，在当前行内的偏移是 p % n。通过这两个值就能直接读取原矩阵，列数 n 才是每行的长度，不能换成行数。

在闭区间 [left, right] 中保存所有还可能包含目标的位置，初始范围是 [0, m * n - 1]。取中点并换算行列坐标后，如果中点值等于目标，直接返回 true。

若中点值小于目标，由整体有序可知中点及其左侧都不可能命中，令 left = mid + 1；若中点值大于目标，则中点及其右侧都可以排除，令 right = mid - 1。每轮都保留目标可能存在的一侧，同时严格缩小范围。

当 left == right 时仍有一个位置需要检查，因此使用 left <= right。两者交错后候选区间为空，说明所有可能位置都已排除，返回 false。整个过程只变化下标，非方阵也使用相同映射，不增加额外存储。

解题步骤

  1. 读取行列数，初始化 left = 0、right = m * n - 1。
  2. 只要 left <= right，计算中点 mid = left + (right - left) / 2。
  3. 从 matrix[mid / n][mid % n] 取得中点值。
  4. 相等时返回 true；小于目标时移动左边界到 mid + 1，大于目标时移动右边界到 mid - 1。
  5. 区间为空仍未命中时，返回 false。

代码实现

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0;
        int right = m * n - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 按列数将一维位置映射回行列，无需真的展平矩阵。
            int value = matrix[mid / n][mid % n];

            if (value == target) {
                return true;
            }

            if (value < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }
}

func searchMatrix(matrix [][]int, target int) bool {
    m, n := len(matrix), len(matrix[0])
    left, right := 0, m*n-1

    for left <= right {
        mid := left + (right-left)/2
        // 按列数将一维位置映射回行列，无需真的展平矩阵。
        value := matrix[mid/n][mid%n]
        if value == target {
            return true
        }
        if value < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

复杂度分析

  • 时间复杂度：$O(\log(mn))$，每轮将 m*n 大小的搜索区间减半。
  • 空间复杂度：$O(1)$，只维护常数个下标变量。

关键点总结

[!green]

  • 两条有序条件合在一起，才能保证按行展开后全局有序。
  • 虚拟下标映射中的除数和模数都是列数 n。
  • 闭区间模板要配套使用：right = m*n-1、left <= right、更新 mid ± 1。
  • 240 题没有“下一行首元素大于上一行末元素”，不能使用整体二分。

易错点总结

[!yellow]

  • 映射时使用行数：一维位置按每行的列数划分，行列转换都应使用 n，否则非方阵会读错位置或越界。
  • 右边界初始化为 m * n：闭区间末端必须是最后一个合法下标 m * n - 1。
  • 循环漏掉等号：单元素候选区间仍需要检查。
  • 更新为 left = mid 或 right = mid：中点已经确认不匹配，应排除它，否则区间可能无法继续缩小。
  • 实际展开矩阵或忽略跨行条件：复制数组需要线性时间和空间；只有行内有序、却没有跨行衔接条件时，也不能对整体二分。

相似题目

题目 难度 关联与区别
240. 搜索二维矩阵 II 中等 原题仅保证行列分别有序，不能展平二分；本题还保证行与行整体相接有序。
35. 搜索插入位置 简单 展平后复用有序数组的下界或查找二分，最后把一维下标映射回行列。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/30863730
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！