面试题4：二维数组中的查找

从右上角为什么特殊开始

先预测：在下面的矩阵中查找7，从左上角1开始，目标更大时该向右还是向下？两个方向都可能。若从右上角9开始，9大于7时却只有一个安全动作：当前列下方都不小于9，因此整列都不可能是7，可以向左。

这道“二维数组中的查找”给出一个矩形矩阵，每行从左到右递增，每列从上到下递增。这里的递增按非递减理解也成立，重复值不会破坏排除逻辑。目标是判断某个整数是否存在，官方实现从右上角开始；左下角是完全对称的另一个起点。

比整体排序弱：把所有元素按行展开后不一定全局有序，因此不能直接对整块内存做一次普通二分。它又比一般矩阵强，足以让边界角点每次排除整行或整列。

为什么不是另外两个角（单调性）

右上角在当前候选区域中，同时是当前行最大值和当前列最小值。若它大于目标，同列下方只会更大，所以删除当前列；若它小于目标，同行左侧只会更小，所以删除当前行。两种比较各自对应唯一动作。

左下角则是当前行最小值、当前列最大值。它大于目标时向上，小于目标时向右，也能保持单向路径。右上角和左下角都可用，选择一个后要让循环边界和移动方向保持一致。

左上角是当前行和当前列的共同最小值。当前值小于目标时，向右和向下都可能命中，无法整行或整列排除；右下角同理。中心点也只能排除一个象限，剩余候选往往分裂成多个区域，失去一条单调路径。

初始覆盖整个矩阵。以右上角搜索时，它可表示为行row..rows-1与列0..column的交叉区域。每一步只删除候选矩形最上面一行或最右边一列。

逐步排除查找 7

作者官方测试矩阵为：

 1   2   8   9
 2   4   9  12
 4   7  10  13
 6   8  11  15

从9开始，9大于7，删除第3列；8仍大于7，删除第2列；2小于7，删除第0行；4小于7，删除第1行；到(2,1)命中7。路径依次为9、8、2、4、7。

给出正确性证明。当前值大于目标时，删除列中的每个值都不小于当前值，不可能等于目标；当前值小于目标时，删除行中的每个值都不大于当前值，也不可能等于目标。命中则直接返回。

若row == rows，说明所有候选行都被删除；若column < 0，说明所有候选列都被删除。候选矩形为空仍未命中，目标不存在。这个终止条件同时控制越界和正确性。

忠实实现扁平连续矩阵

作者接口接收int* matrix、行数和列数，二维矩阵按行连续存储。逻辑坐标(row,column)映射到一维位置row * columns + column，这叫。

#include <cstddef>
#include <span>
 
bool find_in_matrix(
    std::span<const int> matrix,
    std::size_t rows,
    std::size_t columns,
    int target
) {
    if (rows == 0 || columns == 0) {
        return false;
    }
    if (rows > matrix.size() / columns ||
        rows * columns != matrix.size()) {
        return false;
    }
 
    std::size_t row = 0;
    std::size_t column = columns - 1;
    while (row < rows) {
        const int value = matrix[row * columns + column];
        if (value == target) {
            return true;
        }
        if (value > target) {
            if (column == 0) {
                return false;
            }
            --column;
        } else {
            ++row;
        }
    }
    return false;
}

官方代码使用有符号int column，循环条件可以写column >= 0。上面的现代版本用std::size_t，它是无符号类型，不能递减到-1再比较；因此在column == 0且仍需向左时直接返回。类型改变后，边界写法也必须一起改变。

尺寸验证先用除法避免rows * columns在比较前溢出，再确认缓冲区元素数恰好匹配矩形。若接口另有步长或padding，映射应改为row * stride + column，不能继续假定紧密行优先。

嵌套数组要先验证矩形形状

在TypeScript或vector<vector<int>>中，每行是独立容器，可能形成。算法每次用同一个column访问不同行，必须先验证所有行长度相同。

function findInMatrix(
  matrix: readonly (readonly number[])[],
  target: number,
): boolean {
  if (matrix.length === 0 || matrix[0].length === 0) return false;
 
  const columns = matrix[0].length;
  if (matrix.some((row) => row.length !== columns)) return false;
 
  let row = 0;
  let column = columns - 1;
  while (row < matrix.length && column >= 0) {
    const value = matrix[row][column];
    if (value === target) return true;
    if (value > target) column -= 1;
    else row += 1;
  }
  return false;
}

这个函数假定行列单调性由调用者保证。若输入来自外部不可信数据，可以先验证每行与每列，但验证本身要O(mn)，可能高于一次查找成本。真实系统应在数据建立或写入阶段维护不变式，而不是每次查询都重新证明。

复杂度来自路径而不是面积

设矩阵有m行、n列。从右上角开始，row最多增加m次，column最多减少n次；每次循环至少发生一种移动。比较次数上界为m+n-1量级，因此时间复杂度是O(m+n)。

算法只保存行、列、当前值等常数状态，额外空间O(1)。它不会访问所有mn个元素；对于近似方阵，路径长度与边长成正比，而不是与面积成正比。

也不能宣称O(log(mn))。虽然每次排除一整行或一列，但不是每次删除一半候选。若矩阵只有一行，路径最坏可能横向走完所有列；只有额外的全局行间有序条件，才能把矩阵看成整体有序数组二分。

范围外目标会很快沿边界退出。目标小于矩阵最小值时，路径持续向左；目标大于最大值时，路径持续向下。不存在但落在值域内部的5，则会交替移动，最终候选矩形为空。

用反例校验移动方向

移动规则最容易被写反。仍以右上角为起点：当前值大于目标时，如果错误地向下，就进入同一列更大的数字，既没有缩小“过大”方向，也可能直接跳过左侧答案。例如在原矩阵中查找7，从9错误向下会看到12、13、15并退出，真实答案(2,1)从未进入路径。

当前值小于目标时，如果错误地向左，同行左侧只会更小，同样不会接近目标；更严重的是，向左后若删除当前列，就可能丢掉下方较大的候选。每条移动规则都要用“被删除区域为什么全部不可能”等价描述，不能只背“大小决定方向”。

重复值不会破坏算法，只要行列保持非递减。当前值等于目标立即命中；当前值大于目标时，同列下方即使有相同当前值也仍大于目标，可整列删除；当前值小于目标时，同行左侧的相同值仍小于目标，可整行删除。算法不负责返回第一个、最左或全部位置，布尔存在性不要求稳定命中顺序。

单行矩阵退化为从最右端向左扫描：目标较大可能在第一次比较后向下越界，目标较小则最多访问所有列。单列矩阵退化为从顶端向下扫描：目标较小会在首列左越界，目标较大则最多访问所有行。这两个退化例子也说明最坏路径确实可达到m+n量级，不能无条件声称对数时间。

一行为空而其他行非空的嵌套数据不是合法矩形，不能把列数取0后直接返回“目标不存在”，因为这会掩盖输入形状错误。若接口用布尔值合并非法与未找到，至少要在文档中说明；更严格的边界层可先解析成矩形值对象，再让核心查找只接受已验证形状。

多次查询与动态更新的边界

单次查询使用O(m+n)路径很合适。若同一只读矩阵要回答大量查询，可以考虑为每行保存范围并在候选行内二分、建立哈希集合，或在满足更强全局有序条件时按扁平数组二分。预处理会增加构建时间和空间，是否值得取决于查询次数、矩阵大小与更新频率。

矩阵若频繁插入或修改，维护“每行向右不减、每列向下不减”可能比查询本身更难。任意单点更新会同时受左右上下邻居约束；若更新破坏单调性，旧查找会静默漏解，而不一定崩溃。生产系统应把更新验证放在数据结构边界，并用版本或不可变快照保证一次查询期间视图稳定。

并发读取只读快照没有额外问题；若另一个线程在搜索路径经过前后修改元素，排除不变式可能基于互不一致的状态。const或readonly只限制当前函数的写入，不自动冻结共享底层数据。需要锁、复制快照、持久化结构或版本重试来建立一致读取语义。

最后，数值比较还要有全序语义。整数满足；若把算法泛化到浮点数，NaN与任意值比较都不满足普通大小关系，会落入错误分支。泛型版本应要求比较器提供与矩阵构造一致的全序，并用同一比较器验证单调性。

官方测试与更完整回归

作者源码验证：7存在、5不存在、最小值1存在、最大值15存在、0小于最小值、16大于最大值，以及空指针输入。现代嵌套接口还要增加空行、锯齿数组、单行、单列和重复值。

const matrix = [
  [1, 2, 8, 9],
  [2, 4, 9, 12],
  [4, 7, 10, 13],
  [6, 8, 11, 15],
] as const;
 
console.assert(findInMatrix(matrix, 7));
console.assert(!findInMatrix(matrix, 5));
console.assert(findInMatrix(matrix, 1));
console.assert(findInMatrix(matrix, 15));
console.assert(!findInMatrix(matrix, 0));
console.assert(!findInMatrix(matrix, 16));
console.assert(!findInMatrix([], 7));
console.assert(!findInMatrix([[1, 2], [3]], 3));

测试不能只验证布尔结果，还应在可观测版本中记录访问路径，确认每一步行只增、列只减；这能定位移动方向写反、漏掉第0列和row <= rows越界等错误。

本章练习

本章回顾

1. 行列单调矩阵满足每行从左到右递增、每列从上到下递增。
2. 右上角和左下角分别提供两个方向相反的单调性，因此不会产生搜索分叉。
3. 右上角当前值大于目标时排除当前列，小于目标时排除当前行。
4. 候选矩形不变式保证每次排除都不会漏掉仍可能存在的目标。
5. 行坐标只增加、列坐标只减少，时间O(m+n)、额外空间O(1)。
6. 扁平矩阵用row*columns+column映射；嵌套数组必须防御锯齿形状。
7. 有符号与无符号列下标的退出条件不同，不能机械复制column >= 0。
8. 官方测试覆盖命中、缺失、两端、范围外与空输入，工程接口还要覆盖尺寸和单调性契约。

名词解释