有序表查找三劍客：折半、插值與斐波那契查找深度解析

編輯：關於C語言

前提條件：有序 + 順序存儲

所有有序表查找算法要求：關鍵字有序（通常升序）、順序存儲（陣列）支援隨機訪問。若為鏈表，無法 O(1) 定位中間位置，退化為線性查找。

一、折半查找：經典二分法

核心邏輯

區間 [low, high]，初始 [0, n-1]。
mid = (low + high) / 2（防溢出寫法：low + (high - low) / 2）。
比較 key 與 arr[mid]：等 → 成功；小 → high = mid - 1；大 → low = mid + 1。
low > high 結束，失敗。

C 語言實現

int BinarySearch(int *a, int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (key < a[mid]) high = mid - 1;
        else if (key > a[mid]) low = mid + 1;
        else return mid;
    }
    return -1;
}

二、插值查找：基於值分布的自適應中點

核心洞察

折半查找固定取中點 1/2，忽略鍵值分布。插值查找假設鍵值均勻分布，按比例估算位置：

mid = low + ((key - a[low]) * (high - low)) / (a[high] - a[low])

類比查字典：找 "apple" 直接翻前段，而非翻中間。

適用與局限

✅ 鍵值均勻分布、數據量大 → 平均 O(log log n)，極快。
❌ 鍵值分布極度不均（如指數增長）→ 退化至 O(n)，甚至不如折半。
❌ 存在重複鍵值 → 分母為 0 需特殊處理。

三、斐波那契查找：黃金分割點的純整數運算

核心邏輯

利用斐波那契數列 F[k]：0, 1, 1, 2, 3, 5, 8, 13, 21...，滿足 F[k] = F[k-1] + F[k-2]、F[k-1]/F[k] ≈ 0.618（黃金分割）。
擴展陣列至長度 F[k] - 1，尾部填充最大值。
mid = low + F[k-1] - 1，僅需加減法，無乘除，適合早期無硬體乘除器的 CPU。
比較後縮小區間並調整 k：左區間 k -= 1，右區間 k -= 2。

C 語言實現

int FibonacciSearch(int *a, int n, int key) {
    int F[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144};
    int low = 0, high = n - 1, k = 0;
    while (n > F[k]) k++;                 // 找到 F[k] >= n
    for (int i = n; i < F[k] - 1; i++) a[i] = a[n - 1]; // 擴展填充
    while (low <= high) {
        int mid = low + F[k - 1] - 1;
        if (key < a[mid]) { high = mid - 1; k--; }
        else if (key > a[mid]) { low = mid + 1; k -= 2; }
        else return (mid < n) ? mid : n - 1;
    }
    return -1;
}

三算法核心對比

維度	折半查找	插值查找	斐波那契查找
中點計算	`(low+high)/2`	插值公式（乘除）	`low + F[k-1] - 1`（加減）
分布敏感度	無	高（需均勻分布）	無
平均複雜度	O(log n)	O(log log n) 均勻時	O(log n)
最壞複雜度	O(log n)	O(n)	O(log n)
硬體友好度	通用	需乘除器	極高（僅加減）