二维有序矩阵O(N)查找算法咨询：伪代码与时间复杂度分析

核心思路 #

这种每行、每列都递增的矩阵有个关键特性：右上角的元素是当前行的最大值、当前列的最小值（左下角则是当前行最小值、当前列最大值）。利用这个特性可以快速缩小查找范围：

• 若当前元素等于目标，直接返回位置；
• 若当前元素比目标大，目标肯定不在当前列（列从上到下递增），直接左移一列；
• 若当前元素比目标小，目标肯定不在当前行（行从左到右递增），直接下移一行；
• 重复操作直到找到目标或越界（说明目标不存在）。

伪代码实现 #

FUNCTION searchInMatrix(matrix, target):
    N = 矩阵的行数（等于列数）
    row = 0
    col = N - 1  // 起始点设为右上角
    
    WHILE row < N AND col >= 0:
        current = matrix[row][col]
        IF current == target:
            RETURN (row, col)  // 返回目标坐标
        ELSE IF current > target:
            col -= 1  // 左移，排除当前列
        ELSE:
            row += 1  // 下移，排除当前行
    
    RETURN NULL  // 未找到目标

时间复杂度分析 #

最坏情况下，我们需要从右上角遍历到左下角：每次循环只会改变row或col其中一个变量，最多执行2N-1次循环（比如目标比所有元素小，会左移N次；目标比所有元素大，会下移N次；中间情况则是两者的组合）。因此时间复杂度为O(N)，完全符合要求。

空间复杂度为O(1)，仅使用了几个临时变量，没有额外空间开销。

内容的提问来源于stack exchange，提问作者Rafat