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

算法思路 ¶
问题中所说的矩阵在数学上被称为 杨氏矩阵 。
从右上角的视角看矩阵,考虑右上角的顶点 vertex
。

右上角顶点有如下性质:
- 是第一行的最大值
- 是最后一列的最小值
假设要找的数字是 target
:
-
如果
target < vertex
,即target
比最后一列的最小值还要小 , 即可排除最后一列。 -
如果
target > vertex
,即target
比第一行的最大值还要大 , 即可排除第一行。
排除完成后,继续取剩余矩阵的右上角顶点,不断应用此过程:

算法过程:
- 设当前矩阵的顶点为
vertex = matrix[row][col]
,初始条件下:col = cols - 1
,row = 0
。 -
将目标值
target
和顶点的值vertex
进行比较:- 如果
target < vertex
,则排除顶点的列,即col--
。 - 如果
target > vertex
,则排除顶点的行,即row++
。 - 否则,命中结果。
- 如果
-
不断重复前两步,直到无法继续查找为止。
当
row
达到rows
,或者col
递减为0
的时候,结束比较,未找到。
C 语言实现 ¶
有序二维矩阵搜索问题 - 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 。
(完)