n×n行列有序数组：如何实现O(logn)级别的高效搜索？

嘿，这个问题问到点子上了！咱们都知道一维有序数组里二分搜索能做到O(logn)，但行列各自有序的二维数组情况不一样——它不是全局有序的，所以直接套一维二分肯定不行，但我们有两种高效的方法可以用，下面给你详细拆解：

方法一：边角遍历法（线性时间O(n)，最实用） #

这是我个人最推荐的方法，代码简单、常数项小，实际运行效率很高。核心思路是从数组的右上角（或左下角）开始，每次排除一整行或一整列，把搜索范围快速缩小。

拿你给出的示例数组来说：

1   3   7   13  19
2   5   12  14  20
4   9   15  16  22
8   10  18  23  25
11  17  21  24  27

我们从右上角的19开始遍历：

• 如果目标值比当前元素小：说明当前列的所有元素都比目标大（因为每列从上到下递增），直接左移一列
• 如果目标值比当前元素大：说明当前行的所有元素都比目标小（因为每行从左到右递增），直接下移一行
• 找到相等元素就返回存在；如果遍历到数组边界还没找到，说明目标不存在

代码实现（Python） #

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

# 测试示例数组
sample_matrix = [
    [1,3,7,13,19],
    [2,5,12,14,20],
    [4,9,15,16,22],
    [8,10,18,23,25],
    [11,17,21,24,27]
]
print(search_sorted_matrix(sample_matrix, 17))  # 输出 True
print(search_sorted_matrix(sample_matrix, 26))  # 输出 False

这个方法的时间复杂度是O(n)，空间复杂度是O(1)，对于绝大多数场景来说完全够用。

方法二：分治+二分搜索（时间复杂度O(n^log₂3) ≈ O(n^1.58)） #

如果追求理论上更优的时间复杂度，可以试试分治结合二分的思路。核心是把二维数组分成四个象限，通过中间元素快速排除不可能存在目标的象限：

1. 取数组中心位置的元素mid
2. 如果target == mid，直接返回存在
3. 如果target < mid：右下象限的所有元素都比mid大，直接排除，只在左上、右上、左下三个象限递归搜索
4. 如果target > mid：左上象限的所有元素都比mid小，直接排除，只在右上、左下、右下三个象限递归搜索

不过这个方法的代码实现相对复杂，而且递归带来的常数开销可能会抵消理论上的时间优势，所以实际工程中很少用，更多是作为算法思路的拓展。

为什么不能直接用普通二分搜索？ #

这里要注意：行列有序的二维数组不是全局有序的。比如示例数组中第二行第一个元素2，比第一行最后一个元素19小，但比第一行第一个元素1大——整个数组无法直接映射成一个有序的一维数组，所以普通的一维二分搜索完全不适用。

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