Jerry的知识索引

外观

74_搜索二维矩阵[MEDIUM]

约 1215 字大约 4 分钟

2026-02-26

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

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

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

示例 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. 每行内部是有序的（从左到右递增）。
  2. 相邻行之间也是有序的（每行的第一个元素大于上一行的最后一个元素）。

结合这两个条件，我们可以得出一个非常重要的结论：如果将这个二维矩阵按行拼接展平，它实际上就是一个严格递增的一维有序数组。

因此，题目本质上就是让我们在一个有序数据结构中查找特定目标值，这非常适合使用二分查找（Binary Search）。

解题思路

对于这道题，主要有以下三种解法。作为面试官，我通常期待候选人能直接想到前两种，并能清楚地说明第一种解法是最优的。

方法一：全局二分查找（最优解，虚拟一维数组映射）

既然矩阵可以看作一个展开的一维有序数组，我们可以虚拟地把它拉平，直接进行一次二分查找。

  • 假设矩阵有 m 行 n 列，那么总共有 m * n 个元素。
  • 我们将一维数组的索引区间设为 [0, m * n - 1]。
  • 对于一维数组中的任意索引 mid，我们可以通过数学运算将其映射回二维矩阵的坐标：
    • 行号 row = mid / n
    • 列号 col = mid % n
  • 通过坐标拿到矩阵对应的值 matrix[row][col] 后，与 target 比较即可。

复杂度分析：

  • 时间复杂度：O(log⁡(m×n))\mathcal{O}(\log(m \times n))，标准的二分查找时间复杂度。
  • 空间复杂度：O(1)\mathcal{O}(1)，仅使用了常数级别的额外指针。

方法二：两次二分查找

如果考虑到极端情况下矩阵非常大（例如 m×nm \times n 超过了 32 位整数最大值 Integer.MAX_VALUE，当然本题中规模只有 10410^4，不存在此问题），虚拟一维数组的索引可能会溢出。此时可以通过两次二分查找来解决：

  1. 第一步：对矩阵的第一列（或者每一行的最后一个元素）进行二分查找，找到 target 可能落在哪一行。
  2. 第二步：在锁定行内部进行标准的二分查找。 复杂度分析：时间同样是 O(log⁡m+log⁡n)=O(log⁡(mn))\mathcal{O}(\log m + \log n) = \mathcal{O}(\log(mn))，空间 O(1)\mathcal{O}(1)。

方法三：右上角/左下角向内搜索（Z字形搜索）

这是 LeetCode 240题「搜索二维矩阵 II」的经典解法。本题虽然多了一个“下一行首大于上一行尾”的条件，但同样适用。

  • 从矩阵的右上角开始搜索，如果当前值大于目标值，向左移动一列；如果当前值小于目标值，向下移动一行。 复杂度分析：时间复杂度是 O(m+n)\mathcal{O}(m + n)，不如二分查找优，不推荐作为本题的首选。

Java 实现

方法一（全局二分查找）

class Solution {
    /**
     * 搜索二维矩阵
     * 
     * @param matrix 给定的二维矩阵
     * @param target 需要查找的目标值
     * @return 如果 target 存在返回 true，否则返回 false
     */
    public boolean searchMatrix(int[][] matrix, int target) {
        // 防御性编程：处理边界条件
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        
        int m = matrix.length;      // 矩阵的行数
        int n = matrix[0].length;   // 矩阵的列数
        
        // 二分查找的左右边界（将二维矩阵视为长度为 m*n 的一维数组）
        int left = 0;
        int right = m * n - 1;
        
        // 开始标准的二分查找
        while (left <= right) {
            // 防止 (left + right) 导致整型溢出的写法
            int mid = left + (right - left) / 2;
            
            // 核心逻辑：将一维数组的索引转化为二维矩阵的横纵坐标
            // mid / n 得到所在行，mid % n 得到所在列
            int midValue = matrix[mid / n][mid % n];
            
            if (midValue == target) {
                // 找到了目标值
                return true;
            } else if (midValue < target) {
                // 当前值小于目标值，说明目标在右侧（后半部分）
                left = mid + 1;
            } else {
                // 当前值大于目标值，说明目标在左侧（前半部分）
                right = mid - 1;
            }
        }
        
        // 循环结束还未找到，说明 target 不在矩阵中
        return false;
    }
}
贡献者: jerrysheh