华为机试 240：搜索二维矩阵 II 题解

问题描述
给定一个 m x n 的二维矩阵 matrix，其中每一行和每一列均按升序排列。编写一个高效的算法来搜索目标值 target，若存在返回 true，否则返回 false。

示例
输入：

matrix = [
  [1, 4, 7, 11],
  [2, 5, 8, 12],
  [3, 6, 9, 16],
  [10, 13, 14, 17]
],
target = 5

输出：true

方法一：二分查找（逐行或逐列）

对每一行或每一列执行二分查找，利用行列的有序性减少搜索范围。时间复杂度为 O(m log n) 或 O(n log m)，适用于矩阵较小或某一维度较短的情况。

def searchMatrix(matrix, target):
    for row in matrix:
        left, right = 0, len(row) - 1
        while left <= right:
            mid = (left + right) // 2
            if row[mid] == target:
                return True
            elif row[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
    return False

方法二：Z字形搜索（最优解）

从矩阵的右上角或左下角开始搜索，利用行列的单调性逐步缩小范围。时间复杂度为 O(m + n)，空间复杂度为 O(1)。

算法步骤

1. 初始化指针位置为右上角 (i, j) = (0, n-1)。
2. 若 matrix[i][j] == target，返回 true。
3. 若 matrix[i][j] > target，向左移动一列（j -= 1）。
4. 若 matrix[i][j] < target，向下移动一行（i += 1）。
5. 若越界则返回 false。

def searchMatrix(matrix, target):
    if not matrix:
        return False
    m, n = len(matrix), len(matrix[0])
    i, j = 0, n - 1
    while i < m and j >= 0:
        if matrix[i][j] == target:
            return True
        elif matrix[i][j] > target:
            j -= 1
        else:
            i += 1
    return False

方法三：分治算法

将矩阵划分为四个子矩阵，递归搜索目标区域。时间复杂度为 O(n^log3)，但实现较复杂，通常用于理论分析。

关键点总结

• Z字形搜索是本题的最优解法，充分利用行列的单调性。
• 二分查找适用于特定场景，但效率不如Z字形搜索。
• 注意边界条件，如空矩阵或单行/单列矩阵。

练习建议
尝试在左下角起点实现相同逻辑，并对比不同初始点的代码差异。