**楊氏矩陣**：每行左→右遞增，每列上→下遞增。從**右上角** (或左下角) 開始，每次比較可排除一行或一列，時間複雜度 **O(rows + cols)**，空間 **O(1)**。
// 從右上角 (row=0, col=cols-1) 開始
while (row < rows && col >= 0) {
if (matrix[row][col] == target) return true; // 找到
else if (matrix[row][col] > target) col--; // 當前太大，左移 (排除整列)
else row++; // 當前太小，下移 (排除整行)
}
return false; // 越界未找到
#include#include #include bool yang_search(const int *matrix, int rows, int cols, int target) { assert(matrix && rows > 0 && cols > 0); int row = 0; int col = cols - 1; // 右上角起始 while (row < rows && col >= 0) { int current = matrix[row * cols + col]; // 一維索引模擬二維 if (current == target) return true; else if (current > target) col--; else row++; } return false; } int main() { int matrix[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; int targets[] = {7, 5, 10, 0, 9}; for (int i = 0; i < 5; i++) { bool found = yang_search((int*)matrix, 3, 3, targets[i]); printf("查找 %2d: %s\n", targets[i], found ? "存在" : "不存在"); } return 0; }
查找 7: 存在 查找 5: 存在 查找 10: 不存在 查找 0: 不存在 查找 9: 存在
矩陣:
1 2 3
4 5 6
7 8 9
路徑: (0,2)=3 → (1,2)=6 → (2,2)=9 → (2,1)=8 → (2,0)=7 找到
右上 下 下 左 左
3<7 6<7 9>7 8>7 7==7
| 起始點 | 當前 > target | 當前 < target | 可行性 |
|---|---|---|---|
| 右上角 (0, n-1) | 左移 (排除列) | 下移 (排除行) | ✓ 完美 |
| 左下角 (m-1, 0) | 上移 (排除行) | 右移 (排除列) | ✓ 完美 |
| 左上角 (0, 0) | 無法排除 | 右/下雙向 | ✗ 需回溯 |
| 右下角 (m-1, n-1) | 左/上雙向 | 無法排除 | ✗ 需回溯 |
// 完全相同題目，C++ 版
class Solution {
public:
bool searchMatrix(vector>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size(), n = matrix[0].size();
int r = 0, c = n - 1;
while (r < m && c >= 0) {
if (matrix[r][c] == target) return true;
else if (matrix[r][c] > target) c--;
else r++;
}
return false;
}
};
楊氏矩陣查找是**二維有序結構利用單調性**的教科書級範例：**右上角起始、比較即決策、每步排除一行/一列、O(m+n) 最優**。面試必會：起始點選擇理由、邊界條件處理、一維索引映射二維、與二分查找對比、矩陣非完全有序時的變體處理。
