有序二维矩阵搜索问题

问题 ¶

在一个大小为 rows x cols 的二维矩阵中查找目标值 target ， 已知此矩阵的每一行、每一列的数字都是有序的。

leetcode 题目 - 搜索二维矩阵

算法思路 ¶

问题中所说的矩阵在数学上被称为 杨氏矩阵 。

从右上角的视角看矩阵，考虑右上角的顶点 vertex 。

右上角顶点有如下性质：

• 是第一行的最大值
• 是最后一列的最小值

假设要找的数字是 target：

• 如果 target < vertex ，即 target 比最后一列的最小值还要小 ， 即可排除最后一列。

  

• 如果 target > vertex ，即 target 比第一行的最大值还要大 ， 即可排除第一行。

  

排除完成后，继续取剩余矩阵的右上角顶点，不断应用此过程：

算法过程：

1. 设当前矩阵的顶点为 vertex = matrix[row][col] ，初始条件下：col = cols - 1 ，row = 0 。

2. 将目标值 target 和顶点的值 vertex 进行比较：

   1. 如果 target < vertex ，则排除顶点的列，即 col-- 。
   2. 如果 target > vertex ，则排除顶点的行，即 row++ 。
   3. 否则，命中结果。

3. 不断重复前两步，直到无法继续查找为止。

   当 row 达到 rows ，或者 col 递减为 0 的时候，结束比较，未找到。

C 语言实现 ¶

bool SearchSortedMatrix(int rows, int cols, int matrix[rows][cols],
                        int target) {
    if (rows <= 0 || cols <= 0) return false;

    int row = 0;
    int col = cols - 1;
    int vertex = matrix[row][col];

    while (row < rows && col >= 0) {
        if (target < vertex) {
            col--;
        } else if (target > vertex) {
            row++;
        } else {
            return true;
        }
    }
    return false;
}

复杂度分析 ¶

最差情况，找到目标值需要排除 rows 个行， cols 个列，因此时间复杂度是 O(rows + cols) 。

结语 ¶

不过，需要指出，本方法虽然简洁优美，但是不是时间复杂度最优的方法。 参考 Searching a Sorted Matrix Faster 。

（完）