您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

C語言實現楊氏矩陣查找：有序二維數組的高效搜索算法

編輯：關於C語言

C語言實現楊氏矩陣查找：有序二維數組的高效搜索算法

楊氏矩陣（Young Tableau）是指每行左到右遞增、每列上到下遞增的二維數組。在這類矩陣中查找目標值，利用有序特性可達到 O(m+n) 時間複雜度，遠優於暴力 O(mn)。

核心算法思想

從右上角（或左下角）開始：

若當前元素 == target，找到返回
若當前元素 > target，向左移（排除當前列，因該列所有元素都大於 target）
若當前元素 < target，向下移（排除當前行，因該行所有元素都小於 target）

每一步排除一行或一列，最多 m+n-1 步。

完整代碼實現

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

int search_matrix(int *arr, int target, int rows, int cols) {
    if (!arr || rows <= 0 || cols <= 0) return 0;
    
    int row = 0;
    int col = cols - 1;  // 從右上角開始
    
    while (row < rows && col >= 0) {
        int current = arr[row * cols + col];
        if (current == target) {
            return 1;  // 找到
        } else if (current < target) {
            row++;     // 向下：當前行所有元素都小於 target
        } else {
            col--;     // 向左：當前列所有元素都大於 target
        }
    }
    return 0;  // 未找到
}

int main() {
    int arr[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    int target = 7;
    int found = search_matrix((int *)arr, target, 3, 3);
    printf("%s\n", found ? "exist" : "not exist");
    system("pause");
    return 0;
}