二维有序矩阵查找

周子力大约 6 分钟教学文档算法设计与分析分治法递归矩阵查找中等Python

二维有序矩阵查找

题目描述

给定一个 $m$ 行、 $n$ 列的整数矩阵及整数 target，判断目标是否存在。矩阵必须为矩形，每行从左到右、每列从上到下均非递减，允许重复值和负数。返回 True 或 False，不修改矩阵。

行、列下标均从0开始。空矩阵 [] 或所有行均为空的矩形矩阵如 [[], []] 返回 False；行长不一致时抛出 ValueError。输入保证行列有序，代码只检查形状。

示例矩阵：

 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

查找5返回 True，查找20返回 False。注意上一行末尾的15可以大于下一行开头的2，因此不能假设展平成一维后仍然有序。本题使用中间列划分候选区域的递归方法。

题目分析

在中间列寻找分界行

定义 search(top, bottom, left, right)：判断目标是否存在于行区间 $[top,bottom)$ 、列区间 $[left,right)$ 的子矩阵中。空区域返回 False；若目标小于左上角或大于右下角，也可直接排除整个区域。

选中间列 mid，从 top 开始向下扫描，寻找该列第一个不小于目标的元素，其行号记为 row。若等于目标，立即成功。

未找到相等元素时：

row 之前的中间列元素都小于目标。这些行中位于中间列左侧的元素也小于目标，故排除左上区域。
从 row 开始，中间列元素都大于目标。这些行中位于中间列右侧的元素也大于目标，故排除右下区域。
中间列本身已经扫描并排除，剩下左下区域和右上区域需要递归。

剩余区间分别为：

[row,bottom)\times[left,mid),\qquad [top,row)\times[mid+1,right).

若整列均小于目标，row == bottom，左下区域为空；若首元素已大于目标，row == top，右上区域为空。两种情况都由同一组边界处理。

正确性与终止性

排除区域中的每个元素，都能通过行或列的非递减性质证明不等于目标。剩余两块覆盖全部尚未排除的位置，没有遗漏。对子区域重复这个判断，最终找到目标或排除所有候选。

两个子调用都去掉中间列，列数至多约为原来的一半，因此递归一定终止。实际执行时先搜左下区域，成功后利用 or 的短路规则跳过右上区域。

实现代码

Python 中间列分治实现

def search_matrix(matrix, target):
    """前提：每行、每列非递减；检查矩形形状后递归查找。"""
    if not matrix:
        return False
    m, n = len(matrix), len(matrix[0])
    if any(len(line) != n for line in matrix):
        raise ValueError("矩阵各行长度必须一致")
    if n == 0:
        return False

    def search(top, bottom, left, right):
        if top >= bottom or left >= right:
            return False
        if target < matrix[top][left] or target > matrix[bottom - 1][right - 1]:
            return False

        mid = (left + right) // 2
        row = top
        while row < bottom and matrix[row][mid] < target:
            row += 1
        if row < bottom and matrix[row][mid] == target:
            return True

        return (search(row, bottom, left, mid)
                or search(top, row, mid + 1, right))

    return search(0, m, 0, n)


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],
]
for target in [5, 20, 30]:
    print(f"查找 {target}：{search_matrix(matrix, target)}")
print(search_matrix([], 5))

输出：

查找 5：True
查找 20：False
查找 30：True
False

算法执行过程

查找20，区间均为左闭右开。下表列出非空区域的处理；递归遇到空区域直接返回 False。

行区间、列区间	中间列或边界判断	结果或下一步
`[0,5)`、`[0,5)`	第2列为7、8、9、14、23，分界行为4	搜索左下与右上
`[4,5)`、`[0,2)`	第1列为21，分界行为4	搜索左下单元18；右上为空
`[4,5)`、`[0,1)`	区域最大值18小于20	返回 `False`
`[0,4)`、`[3,5)`	第4列为15、19、22、24，分界行为2	搜索左下与右上
`[2,4)`、`[3,4)`	区域最大值17小于20	返回 `False`
`[0,2)`、`[5,5)`	列区间为空	返回 `False`

根调用的两块候选都失败，因此20不存在。查找5时，根调用在第2列的首元素7处停止，进入列区间 [0,2)；其中间列为第1列，向下检查4、5后返回成功。

复杂度分析

按整数比较和矩阵元素访问为单位成本。以下结论针对本篇的中间列分治实现。

时间复杂度： 非空矩阵的上界为 $O(m\log(n+1))$ ，含形状检查的 $O(m)$ 。每层递归的非空子区域拥有互不重叠的行区间，所以这一层扫描的行数合计不超过 $m$ ；列区间至多经过 $O(\log(n+1))$ 层。非空调用的边界工作及空子调用也受同层非空区域数控制。这里没有把矩阵查找写成一维二分的 $O(\log(mn))$ 。

辅助空间复杂度： $O(\log(n+1))$ ，来自递归调用栈；通过下标引用原矩阵，不复制子矩阵。输出是一个布尔值，占 $O(1)$ 空间。

[] 的处理为 $O(1)$ ； $m$ 个空行仍需形状检查，时间为 $O(m)$ ，辅助空间为 $O(1)$ 。从右上角逐行或逐列排除的另一种方法可做到 $O(m+n)$ 时间、 $O(1)$ 辅助空间，但其执行结构与本篇不同，应分别分析。

易错点

展平后直接二分。 行列分别有序不保证前一行末尾小于后一行首元素。
只保留一个象限。 未命中时，左下和右上都可能含有目标，需要分别搜索。
重复搜索中间列。 当前层已排除该列，右上子区域从 mid + 1 开始。
对空区域读取角元素。 必须先检查区间为空，再读取左上角和右下角。
把列数减半理解为总时间对数级。 一层可能扫描多行，且可能存在两个子调用。

课堂练习

在 [[1, 4, 7], [2, 5, 8], [3, 6, 9]] 中查找8，根调用排除后保留哪块区域？
[[1, 2], [1, 3]] 能否展平后二分？每行、每列是否满足题设？
查找 [[2, 2], [2, 2]] 中的2和3，分别返回什么？
在只有一列、含 $m$ 行的矩阵中，本实现的时间上界是什么？

参考答案

中间列为第1列，4、5、6均小于8，分界行等于3。左下为空，保留全部3行的第2列；扫描7、8后找到目标。
展平为 [1, 2, 1, 3]，不满足一维非递减顺序，不能直接二分。但原矩阵的每行、每列都非递减，满足本题条件。
查找2返回 True；查找3在根区域的最大值检查处返回 False。
$O(m)$ 。虽然列分治只有一层，扫描这一列仍可能访问 $m$ 个元素。