240. 搜索二维矩阵 II

题目链接（中等）

题目描述

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

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

数据范围：

• m == matrix.length
• n == matrix[i].length
• 1 <= n, m <= 300
• -10^9 <= matrix[i][j] <= 10^9
• 每行的所有元素从左到右升序排列
• 每列的所有元素从上到下升序排列
• -10^9 <= target <= 10^9

示例

示例 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

核心思路

矩阵有两个关键性质：

• 每行从左到右递增；
• 每列从上到下递增。

因此可以设计比暴力遍历更快的算法。三种常见做法：

1. 暴力遍历：逐个检查，时间 $O(mn)$；
2. 逐行二分：每行二分查找，时间 $O(m \log n)$；
3. Z 字形查找：从右上角出发，每次排除一行或一列，时间 $O(m+n)$。

其中 Z 字形查找是本题最优解法，也最能体现矩阵有序性的利用。

---

方法一：逐行二分查找

思路及解法

因为每一行都是升序的，可以对每一行单独做一次二分查找。

Python 可以用 bisect_left：

• 找到第一个 >= target 的位置 idx；
• 若 idx 在行内且 row[idx] == target，返回 True。

代码

from bisect import bisect_left

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        for row in matrix:
            idx = bisect_left(row, target)
            if idx < len(row) and row[idx] == target:
                return True
        return 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])
        
        for i in range(m):
            if matrix[i][0] > target:
                break
            if matrix[i][n - 1] < target:
                continue

            lo, hi = 0, n - 1
            while lo <= hi:
                mid = (lo + hi) // 2
                if matrix[i][mid] == target:
                    return True
                elif matrix[i][mid] < target:
                    lo = mid + 1
                else:
                    hi = mid - 1
        
        return False

复杂度分析

• 时间复杂度：$O(m \log n)$，对每行二分一次。
• 空间复杂度：$O(1)$。

---

方法二：Z 字形查找（推荐）

思路及解法

从矩阵的右上角 (0, n-1) 出发，每次比较 matrix[x][y] 与 target：

• 若相等，直接返回 True；
• 若 matrix[x][y] > target：由于第 y 列从上到下递增，当前元素已经是该列最小的，且它比 target 大，所以整列都大于 target，可以排除这一列，令 y -= 1；
• 若 matrix[x][y] < target：由于第 x 行从左到右递增，当前元素已经是该行最大的，且它比 target 小，所以整行都小于 target，可以排除这一行，令 x += 1。

每一步都会排除一整行或一整列，x 最多增加 m 次，y 最多减少 n 次，因此总步数不超过 m + n。

为什么从右上角开始？

• 右上角是「本行最大、本列最小」的位置，两个方向的单调性刚好相反，可以据此决定排除行还是列；
• 如果从左下角开始，也有类似性质（本行最小、本列最大），同样可行；
• 但从左上角或右下角出发则不行，因为两个方向都是同向递增或递减，无法确定排除哪一侧。

代码

class Solution:
    def searchMatrix(self, matrix: list[list[int]], target: int) -> bool:
        m, n = len(matrix), len(matrix[0])
        x, y = 0, n - 1                  # 从右上角出发

        while x < m and y >= 0:
            if matrix[x][y] == target:
                return True
            if matrix[x][y] > target:
                y -= 1                   # 排除当前列
            else:
                x += 1                   # 排除当前行

        return False

复杂度分析

• 时间复杂度：$O(m + n)$，x 最多增加 m 次，y 最多减少 n 次。
• 空间复杂度：$O(1)$，只用两个指针。

---

与 LC 74 的区别

• LC 74. 搜索二维矩阵：矩阵整体按行展开是一个一维有序数组，可以用一次二分，时间 $O(\log(mn))$；
• LC 240：只保证「行有序 + 列有序」，不能用整体二分，但可以用 Z 字形查找做到 $O(m+n)$。

相关题目

• LC 74. 搜索二维矩阵（整体有序，一次二分）
• LC 378. 有序矩阵中第 K 小的元素（堆 / 二分答案）
• LC 1351. 统计有序矩阵中的负数（Z 字形变形）