240. 搜索二维矩阵 II (Medium)

专题归类： 矩阵 · 二分查找 LeetCode 链接： https://leetcode.cn/problems/search-a-2d-matrix-ii/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

• 每行的元素从左到右升序排列
• 每列的元素从上到下升序排列

示例 1：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

补充说明：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• -10^9 <= target <= 10^9

---

题目详细分析

数据范围分析：

• 矩阵最大 300×300 = 90000 个元素，暴力搜索 O(m×n) 约 9 万次，其实不会超时。但作为经典题，O(m+n) 是标准解法。
• 元素值和 target 的范围很大（±10

输入输出特征：

• 输入是二维矩阵（m×n，但不一定是方阵）和目标值，输出是布尔值。
• 矩阵的排序特性：每行从左到右升序、每列从上到下升序。注意：这和 74-搜索二维矩阵 不同——本题的下一行首元素不一定大于上一行末元素（只是每列从上到下升序）。

边界条件：

• 矩阵只有一行或一列 → 相当于一维数组的二分查找。
• 矩阵为空（题目说 m,n >= 1，但可以做防御性检查）。
• target 小于最小元素或大于最大元素 → 直接返回 false。
• target 恰好是某个重复元素之一 → 只要存在就返回 true。

隐藏条件：

• 矩阵的排序特性比”每行都排序”更强——列也是排序的。这意味着右上角（或左下角）是一个”分水岭”：它是所在行的最大值、所在列的最小值。
• 虽然每次只能排除一行或一列，但 O(m+n) 已经比 O(m×n) 好很多。
• 这个矩阵性质不能直接对整个矩阵做一次二分查找。

---

小白版直白理解

想象你有一个超级大的书架，书架上每行从左到右价格递增，每列从上到下价格递增。你想找一本特定价格的书。

笨办法： 一本本看（暴力搜索），太慢了。

聪明法（右上角法）： 从书架的右上角开始找。这个位置很特殊——它既是这一行中最贵的书，又是这一列中最便宜的书。

• 如果目标价格 > 当前书的价格：因为当前是这一行中最贵的，这一行其他书都更便宜，肯定找不到目标，所以向下走到下一行。
• 如果目标价格 < 当前书的价格：因为当前是这一列中最便宜的，这一列其他书都更贵，肯定找不到目标，所以向左走到前一列。
• 如果价格相等：找到了！

每走一步就排除一整行或一整列，最多走 m+n 步就能找遍整个书架。

---

解题思路

思路一：右上角搜索法（推荐）

核心洞察：

从右上角 (0, n-1) 出发，利用行列单调性：

• matrix[row][col] > target → 当前元素太大了，该列下面的元素都更大，排除当前列，col--
• matrix[row][col] < target → 当前元素太小了，该行左边的元素都更小，排除当前行，row++
• matrix[row][col] == target → 找到

为什么是右上角而不是左上角？ 从左上角 (0, 0) 出发，它的右边和下边都比它大，无法判断往哪边走。右上角的特殊性在于它既是行的最大值又是列的最小值，有确定的”大→左移，小→下移”规则。

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    m, n = len(matrix), len(matrix[0])
    row, col = 0, n - 1  # 从右上角出发
    
    while row < m and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            col -= 1  # 排除当前列
        else:
            row += 1  # 排除当前行
    
    return False

复杂度： O(m + n) 时间，O(1) 空间。

思路二：左下角搜索法

和右上角对称。从左下角 (m-1, 0) 出发：

• 当前值 > target → 上移（排除当前行）
• 当前值 < target → 右移（排除当前列）

def searchMatrix_bottomLeft(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    m, n = len(matrix), len(matrix[0])
    row, col = m - 1, 0  # 从左下角出发
    
    while row >= 0 and col < n:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] > target:
            row -= 1  # 排除当前行
        else:
            col += 1  # 排除当前列
    
    return False

思路三：逐行二分查找

对每行做一次二分查找。如果矩阵行数远少于列数（m << n）或列数远少于行数（n << m），这种方法可能比 O(m+n) 更好。

def searchMatrix_binary(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    import bisect
    
    for row in matrix:
        # 对每一行做二分查找
        idx = bisect.bisect_left(row, target)
        if idx < len(row) and row[idx] == target:
            return True
    
    return False

复杂度： O(m × log n) 或 O(n × log m)，选择行数较少的维度。

思路四：四分法 / 分治法（进阶）

将矩阵分成四个象限，利用行列排序特性排除不可能包含 target 的象限。

• 如果 matrix[mid_row][mid_col] < target → 左上角象限可以排除（都小于 target）
• 如果 matrix[mid_row][mid_col] > target → 右下角象限可以排除（都大于 target）

def searchMatrix_divide(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    def search(r1, r2, c1, c2):
        """在子矩阵 [r1..r2][c1..c2] 中搜索"""
        if r1 > r2 or c1 > c2:
            return False
        if target < matrix[r1][c1] or target > matrix[r2][c2]:
            return False
        
        mid_r = (r1 + r2) // 2
        mid_c = (c1 + c2) // 2
        
        if matrix[mid_r][mid_c] == target:
            return True
        elif matrix[mid_r][mid_c] > target:
            # 排除右下角，搜索其他三个象限
            return (search(r1, mid_r - 1, c1, c2) or
                    search(mid_r, r2, c1, mid_c - 1))
        else:
            # 排除左上角，搜索其他三个象限
            return (search(mid_r + 1, r2, c1, c2) or
                    search(r1, mid_r, mid_c + 1, c2))
    
    return search(0, len(matrix) - 1, 0, len(matrix[0]) - 1)

---

易错点

• 越界检查：while row < m and col >= 0 或 while row >= 0 and col < n，一不小心就索引越界。
• 空矩阵：虽然题目说 m,n >= 1，但养成防御性检查的习惯总没错。
• 与 74 题混淆：74-搜索二维矩阵 中矩阵是”下一行首大于上一行末”，可以当成一维数组直接二分。本题的矩阵没有这个性质，不能直接二分。
• 二分法的适用条件：逐行二分的做法需要每行有序，本题确实满足，但不是最优解。
• 右上角 vs 左上角：千万不要从左上角开始搜索——两边都比当前值大，无法判断方向。
• 重复元素：矩阵可以包含重复元素（题目没说唯一），但搜索找到任意一个即可。

---

框架提炼

Zigzag 搜索模板（有序矩阵搜索）：

def searchMatrix(matrix, target):
    if not matrix or not matrix[0]:
        return False
    
    # Step 1: 选择起点（右上角或左下角）
    row, col = 0, len(matrix[0]) - 1  # 右上角
    
    # Step 2: 循环搜索，每次排除一行或一列
    while row < len(matrix) and col >= 0:
        current = matrix[row][col]
        
        if current == target:
            return True
        elif current > target:
            col -= 1      # 排除当前列
        else:  # current < target
            row += 1      # 排除当前行
    
    return False

适用条件：

• 矩阵的每行从左到右升序
• 矩阵的每列从上到下升序

这类问题的共同特征： 利用”分水岭”位置（右上角或左下角）来缩小搜索范围。每次比较都可以排除一行或一列，从而在 O(m+n) 时间内完成搜索。

---

关联题目

• 74-搜索二维矩阵 — 本题的”表亲”。74 的矩阵性质更强（每行首元素大于上一行末元素），可以直接把矩阵展平做二分查找。而本题的矩阵性质更弱（只有行列各自有序），只能用右上角法。
• 33-搜索旋转排序数组 — 一维搜索的变体，搜索旋转排序数组。与本题共享”利用部分有序信息缩小搜索范围”的思想。
• 378-有序矩阵中第K小的元素 — 在本题的有序矩阵中找到第 K 小的元素，可以用二分值域法（对值做二分）+ 右上角法计数。
• 1351-统计有序矩阵中的负数 — 同样利用矩阵行列有序特性，从右上角出发统计负数个数。