插值搜尋

插值搜尋會比較目標值與目前範圍兩端的值，估算目標所在的位置。在已排序且數值分布大致均勻的資料中，這種依值估算的探查方式，找到目標所需的探查次數可能少於每次都檢查中間位置的二分搜尋。如果數值集中在某些區段或間距不均，這種估算就沒那麼有效，因此數值分布的假設很重要。可以用查字典來理解：尋找以「s」開頭的單字時，會先從較靠近後面的頁數開始翻，而不是從中間開始，再根據看到的內容縮小範圍。

插值搜尋演算法

對於遞增排序的陣列 A 和目標 X，維護包含端點的界限 lo 和 hi，初始值分別是第一個與最後一個索引。陣列必須已排序；否則，範圍比較與探查位置估算都無法安全地排除數值。當 X 落在 A[lo] 和 A[hi] 之間時，使用下式估算位置：

mid = lo + (X - A[lo]) * (hi - lo) / (A[hi] - A[lo])

計算使用整數除法，因此估算結果是陣列索引。如果 A[mid] 小於 X，就從 mid + 1 繼續；如果大於 X，就從 mid - 1 繼續；如果相等，就回傳 mid。進行估算前，先處理兩端值相同的情況：若該值等於 X，就回傳其中一端的索引；否則，目標不可能出現在這個範圍內。當界限交錯時停止。若目標小於目前範圍的端點值或大於端點值，也可以立即判定找不到。這些檢查可避免除以零，也能避免存取空範圍。

插值搜尋範例

考慮 A = (1, 3, 7, 8, 11, 15, 17, 18, 21)，目標為 X = 18。初始時，lo = 0、hi = 8、A[lo] = 1，而 A[hi] = 21。經過整數除法後，估算位置為 0 + (18 - 1) * (8 - 0) / (21 - 1) = 6。由於 A[6] = 17 小於目標，將 lo 設為 7。下一次估算為 7 + (18 - 18) * (8 - 7) / (21 - 18) = 7。此時 A[7] = 18，因此搜尋回傳索引 7。

插值搜尋演算法實作

以下是完整的 C++ 範例，使用與追蹤過程相同的數值和目標。找到目標時，函式會回傳從零開始計算的索引；找不到時則回傳 -1。程式碼與輸出區塊中的可見標籤維持英文，因為這些區塊必須與英文原文完全一致。

執行此範例：

本節中的程式碼以及顯示的標籤或輸出仍為英文。

#include <iostream>
#include <limits>
#include <vector>

static_assert(std::numeric_limits<int>::digits <= 31,
              "This implementation supports int types up to 32 bits");

int interpolationSearch(const std::vector<int>& values, int target) {
    if (values.empty() ||
        values.size() > static_cast<std::size_t>(std::numeric_limits<int>::max())) {
        return -1;
    }

    int lo = 0;
    int hi = static_cast<int>(values.size()) - 1;
    while (lo <= hi && target >= values[lo] && target <= values[hi]) {
        if (values[lo] == values[hi]) {
            return values[lo] == target ? lo : -1;
        }

        const int mid = lo + static_cast<int>(
            ((static_cast<long long>(target) - static_cast<long long>(values[lo])) *
             (hi - lo)) /
            (static_cast<long long>(values[hi]) -
             static_cast<long long>(values[lo])));

        if (values[mid] == target) return mid;
        if (values[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

int main() {
    const std::vector<int> values{1, 3, 7, 8, 11, 15, 17, 18, 21};
    const int target = 18;
    const int result = interpolationSearch(values, target);
    if (result >= 0) std::cout << "Element found at index " << result << '\n';
    else std::cout << "Element not found\n";
}

Element found at index 7

防護條件涵蓋元素數量為零、目標超出目前數值範圍，以及範圍兩端的值相同等情況。此實作要求 int 不超過 32 位元，且向量最多包含 INT_MAX 個元素；轉換索引為 int 前會先檢查大小。每次相減前都先將兩個值轉型為 long long，可確保在完整的 32 位元 int 範圍內，分子差值與分母都安全。分子乘積的最大值為 (2^32 - 1) * (INT_MAX - 1)，可容納於帶正負號的 64 位元 long long；商介於零與 hi - lo 之間，因此加到 lo 後仍在界限內。輸入仍必須依遞增順序排序。此範例可獨立使用，不需要其他檔案。

插值搜尋演算法複雜度

時間複雜度

最佳情況為 O(1)：第一次估算的位置就是目標所在處。若已排序範圍內的數值分布大致均勻，平均時間為 O(log log n)，因為每次依值估算通常都能大幅縮小區間。這項平均情況的結果取決於數值分布的假設，並不保證適用於每個已排序陣列。

最差情況為 O(n)。如果依值估算的位置反覆無法有效縮小範圍，演算法可能需要檢查線性數量的位置。數值分布極不均勻時就可能發生這種情況；若分布未知或不規則，二分搜尋可能是較容易預測的選擇。

空間複雜度

迭代式實作只使用固定數量的純量變數，因此輔助空間為 O(1)。它不會配置另一個陣列，也不會使用遞迴。