插補搜尋法(Interpolation Search)

昨天我們看完 二分搜 後，今天要來繼續學另一個搜尋法 : 插補搜尋法(Interpolation Search)，插補搜尋法是二分搜的改良版，在資料均勻分布時能比 二分搜 有更好的平均效能

什麼是插補搜尋法?

*圖片連結(https://www.istockphoto.com/hk/%E5%9C%96%E7%89%87/%E5%AD%97%E5%85%B8)

假設有一本按照頁碼排列的字典：

1, 2, 3, 4, 5, ..., 1000

如果要找第 900 頁，你大概不會直接翻到中間的第 500 頁開始找，而是會覺得：
900 離 1000 很近，所以應該在後面的位置，插補搜尋法也是同樣的概念。

它利用資料的分布情況，估算目標值可能出現的位置，而不是固定從中間開始搜尋

公式 :
pos = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left])

光看公式和圖片我覺得還是不夠直觀，所以我們用以下的例子來看~

索引: 0   1   2   3   4   5   6   7   8

數值: 10  20  30  40  50  60  70  80  90

假設我們要找 target = 80
那已知 arr[0]=10，arr[8]=90
接下來就畫和上面一樣的座標~

從斜率得知 : 每增加 1 個索引，數值平均增加 10

既然數值平均分布，所以可以知道 (target - arr[left]) / pos - left = 斜率，
將式子整理過後會發現就是我們上面的公式

那我們直接帶入上面公式: pos = left + (target - arr[left]) * (right - left) / (arr[right] - arr[left])

所以直接猜 pos = 7，剛好就是正確答案

補充 : 公式整理過程

交叉相乘移項

兩邊同乘斜率倒數

最終公式

為什麼均勻分布時可以猜到

例如 : 10 20 30 40 50 60 70 80 90 數值和位置幾乎是線性關係，
所以可以用斜率推估

什麼時候失效？

例如 : 1 2 3 4 5 6 7 8 1000000，算出來的猜測位置會嚴重偏移，例如target = 8
公式會一直認為 target 靠近左邊，因此算出的 pos 幾乎都卡在前面幾個位置，最差可能退化到 O(n)，反而比二分搜尋法還慢

程式碼

#include <iostream>
using namespace std;

int interpolationSearch(int arr[], int n, int target) {
    int left = 0, right = n - 1;

    while (left <= right && target >= arr[left] && target <= arr[right]) {
        // 如果左右邊界值相同，避免除以 0
        if (arr[left] == arr[right]) {
            if (arr[left] == target) return left;
            break;
        }

        // 公式
        int pos = left + (long long)(target - arr[left]) * (right - left) / (arr[right] - arr[left]);

        if (arr[pos] == target) {
            return pos; // 找到目標
        } else if (arr[pos] < target) {
            left = pos + 1; // 目標在右半邊
        } else {
            right = pos - 1; // 目標在左半邊
        }
    }

    return -1; 
}

int main() {
    int arr[] = {10, 20, 25, 35, 42, 50, 63, 78, 91, 100};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 63;

    int result = interpolationSearch(arr, n, target);

    if (result != -1)
        cout << "找到目標 " << target << " 索引位置為 " << result << endl;
    else
        cout << "找不到目標 " << target << endl;

    return 0;
}

和二分搜比較

複雜度

平均情況 : O(log log n)
最壞情況 : O(n)
空間複雜度 : O(1)

我們明天會來看雜湊表，並把之前寫的Two sum的程式優化 ~~

參考資料和書籍

1. 【演算】內插搜尋法 - Interpolation Search _by Infinite loop