C語言二維陣列查找：楊氏矩陣搜尋演算法實作

問題描述

給定一個 3x3 的二維陣列，其中每列由左至右遞增、每行由上至下遞增（即楊氏矩陣特性）。請撰寫函式判斷目標數值是否存在於陣列中。

原始程式碼分析

提供的程式碼將二維陣列視為一維陣列線性掃描，且只檢查數值 `<= 9`，這並未利用楊氏矩陣的有序特性，時間複雜度為 O(n²)，且邏輯有誤（若陣列值超過 9 會提早結束）。

正確解法：右上角搜尋法（或左下角）

利用矩陣「行遞增、列遞增」特性，從右上角 (0, n-1) 開始：

• 若當前值 == 目標 → 找到，回傳 true。
• 若當前值 > 目標 → 往左移（列索引 -1），因為該列下方更大。
• 若當前值 < 目標 → 往下移（行索引 +1），因為該行左邊更小。
• 超出邊界仍未找到 → 不存在。

時間複雜度 O(m+n)，空間複雜度 O(1)。

完整可執行程式碼

#include 
#include 

bool searchMatrix(int matrix[3][3], int rows, int cols, int target) {
    int row = 0;
    int col = cols - 1;  // 從右上角開始

    while (row < rows && col >= 0) {
        int current = matrix[row][col];
        if (current == target) return true;
        else if (current > target) col--;   // 往左
        else row++;                         // 往下
    }
    return false;
}

int main() {
    int arr[3][3];
    printf("請輸入 3x3 矩陣元素（每列遞增、每行遞增）：\n");
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            scanf("%d", &arr[i][j]);

    int target;
    printf("請輸入要查找的數值：");
    scanf("%d", &target);

    if (searchMatrix(arr, 3, 3, target))
        printf("yes!\n");
    else
        printf("no!\n");

    return 0;
}

進階：泛型版本（任意尺寸）

bool searchYangMatrix(int *matrix, int rows, int cols, int target) {
    int row = 0, col = cols - 1;
    while (row < rows && col >= 0) {
        int val = matrix[row * cols + col];
        if (val == target) return true;
        else if (val > target) col--;
        else row++;
    }
    return false;
}

將二維陣列攤平成一維指標傳遞，配合 `row * cols + col` 索引，適用於動態配置或不固定大小的矩陣。

測試案例

輸入矩陣：
1 2 3
4 5 6
7 8 9
查找 5 → yes!
查找 10 → no!

總結

楊氏矩陣搜尋是經典面試題。關鍵在於識別「有序矩陣」特性，選擇正確的起始點（右上或左下）進行單向刪減搜尋空間，達到 O(m+n) 最佳複雜度。切勿退化為暴力線性掃描。