C語言二維數組查找：楊氏矩陣的另一種實現視角

編輯：關於C語言

C語言二維數組查找：楊氏矩陣的另一種實現視角

本文展示一種基於一維掃描的楊氏矩陣查找實現。雖然未充分利用矩陣有序特性（時間複雜度 O(mn)），但代碼簡潔，適合小規模數據或教學演示。

代碼實現

#include <stdio.h>
#include <assert.h>

int find_Num(int *arr, int n) {
    assert(arr);
    while (*arr <= 9) {  // 假設矩陣最大值為 9，防止越界
        if (*arr == n) {
            return 1;
        }
        arr++;
    }
    return 0;
}

int main() {
    int n, m, i, j;
    int arr[3][3] = {0};
    
    // 輸入 3x3 矩陣
    for (i = 0; i < 3; i++)
        for (j = 0; j < 3; j++)
            scanf("%d", &arr[i][j]);
    
    scanf("%d", &n);
    m = find_Num((int *)arr, n);
    
    if (m == 1) {
        printf("yes!\n");
    } else {
        printf("no!\n");
    }
    return 0;
}

代碼分析

將二維數組視為一維連續內存，通過指針遞增遍歷
*arr <= 9 作為終止條件，實際應用中應傳入行列數計算邊界
未利用行列有序特性，屬於線性掃描

改進建議

// 正確的一維掃描版本（帶邊界）
int find_Num_v2(int *arr, int target, int rows, int cols) {
    int total = rows * cols;
    for (int i = 0; i < total; i++) {
        if (arr[i] == target) return 1;
    }
    return 0;
}

// 推薦：利用有序特性的 O(m+n) 版本（見文章 194918）
int find_Num_optimal(int *arr, int target, int rows, int cols) {
    int row = 0, col = cols - 1;
    while (row < rows && col >= 0) {
        int val = arr[row * cols + col];
        if (val == target) return 1;
        else if (val < target) row++;
        else col--;
    }
    return 0;
}