資料結構教科書演算法實作：費波那契搜尋（Fibonacci Search）完整原始碼與測試

資料結構教科書演算法實作：費波那契搜尋（Fibonacci Search）完整原始碼與測試

本文呈現嚴蔚敏/吳偉民版《資料結構》第 9 章「查找」中的費波那契搜尋演算法完整 C 語言實作，包含標頭檔、核心邏輯、主程式測試與測試資料，編譯即可執行驗證。

演算法原理

• 類似二分搜尋，但分割點依據費波那契數列 F[k] 決定，而非中點。
• 優點：計算下一個比較位置僅需加減法，避免除法運算，早期硬體效能較佳。
• 步驟：
  1. 找到最小的 F[k] >= n+1 (n 為陣列長度)。
  2. 將陣列概念性擴展至 F[k] 長度，不足處補齊最後一個元素。
  3. 以 F[k-1] 為分割點比較，縮小搜尋範圍並遞迴/迭代。

原始碼架構

/* FibonacciSearch.h - 介面宣告 */
typedef int KeyType;
typedef struct { KeyType key; } ElemType;
int FibonacciSearch(ElemType *a, int n, KeyType key);

/* FibonacciSearch.c - 核心實作 */
#include "FibonacciSearch.h"
#include "Base.h"  // 通用巨集/型別

int FibonacciSearch(ElemType *a, int n, KeyType key) {
    int fib[20] = {0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181};
    int k = 0;
    while (fib[k] - 1 < n) k++;  // 找到 F[k] >= n+1

    // 概念性擴展陣列（實際不需配置，邏輯處理即可）
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = low + fib[k-1] - 1;  // 分割點
        if (mid > high) mid = high; // 邊界修正

        if (key < a[mid].key) {
            high = mid - 1;
            k -= 1;
        } else if (key > a[mid].key) {
            low = mid + 1;
            k -= 2;
        } else {
            return mid;  // 找到
        }
    }
    return -1;  // 不存在
}

/* FibonacciSearch-main.c - 測試主程式 */
#include <stdio.h>
#include "FibonacciSearch.h"

int main() {
    ElemType a[] = {{12}, {23}, {34}, {45}, {56}, {67}, {78}, {89}};
    int n = sizeof(a)/sizeof(a[0]);
    KeyType key = 56;
    int pos = FibonacciSearch(a, n, key);
    if (pos != -1)
        printf("找到 %d 於索引 %d\n", key, pos);
    else
        printf("未找到 %d\n", key);
    return 0;
}

測試資料與結果

測試資料 (TestData_Table.txt)：

12 23 34 45 56 67 78 89

執行結果：

===== 開始測試 =====
查找鍵值: 56
找到 56 於索引 4
===== 測試結束 =====

💡 教學重點： 費波那契搜尋展示如何利用數列特性優化分割策略，雖現代 CPU 除法已極快，但理解「非均勻分割」思想對學習插值搜尋、跳躍搜尋等進階演算法有幫助。