演算法知識 - 插值搜尋 inerpolation search

2021-06-01

字數統計： 665 | 閱讀時間≈ 2分鐘

插值搜尋 inerpolation search 介紹與實作原理

插值搜尋主要用在於資料量大，且資料離散程度大致相同的數列。

其概念與二分搜尋 by 大衞的筆記概念大致相同，只有對於 mid 並不同。

二分搜尋再分成左右子樹時，是切半分配。
插值搜尋則是透過斜率公式去進行優化。

其主要插值法的選擇原理如下
value 是我們要查詢的值，那 \(x_1, x_2\) 則是我們現在進行搜尋的區間，因為我們要搜尋的數列是已經排序好的數列，那我們假設區間的資料都是相同離散分布，因此理論上我們可以透過斜率來猜測我們的 value 應該位於 m 處(數列 index)。
也就是我們透過 \(m = \frac{(value - y_1)(x_2 - x_1)}{(y_2 - y_1)} + x_1\)。

插值搜尋 inerpolation search 程式碼說明與應用

透過程式碼來進行說明相信會更好理解，以下我們示範搜尋 4 這個位置。

由於我們資料離散程度相當，因此只需要一次我們就可以成功找到。


#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int num[] = {1,2,3,4,5,6,7,8,9,10}; //已經排序好的數列 
int num_size; //數列長度

int interpolation_search(int val){ //val 要查詢的值
    int L = 0; //左邊界
    int R = num_size-1; //右邊界
    int cnt = 0;
    cout << "interpolation search start.\n";

    while(R >= L){ //如果右邊界 >= 左邊界，就繼續執行
        //斜率優化公式找出 mid
        int mid = L + (val-num[L]) * (R-L) / (num[R]-num[L]);
        cout << ++cnt << " search. find " << num[mid] << '\n';
        if(num[mid] == val) return mid; //如果成功找到，就輸出 index
        //如果 num[mid] > val，表示資料在左邊界，那就將左邊界改為 mid+1
        if(num[mid] > val) L = mid+1;
        //如果 num[mid] < val，表示資料在右邊界，那就將右邊界改為 mid+1 
        if(num[mid] < val) R = mid; 

    }
    cout << "cat't find " << val << "\n"; 
    return -1; //無法找到，輸出 -1

}

int main()
{
    num_size = sizeof(num) / sizeof(num[0]);
    int val = 4;
    cout << val << " position is " << interpolation_search(val) << '\n';
    return 0;
}