插值搜尋

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 插值搜尋演算法
  2. 插值搜尋示例
  3. 插值搜尋演算法的實現
  4. 插值搜尋演算法的複雜度
插值搜尋

插值搜尋是一種快速高效的搜尋演算法。它改進了二叉搜尋演算法,適用於陣列元素均勻分佈在排序陣列上的場景。它的工作原理是探測所需值的位置。與二叉搜尋不同的是,它並不總是去陣列的中間,而是可能根據要搜尋的鍵值去任何位置。我們比較估計位置的值,並將搜尋空間縮小到它之後或之前的部分。例如,當我們在字典中搜尋一個單詞時,我們根據裡面字母的位置來翻頁,而不是每次都把搜尋空間分成兩半。

插值搜尋演算法

假設我們有一個未排序的陣列 A[],包含 n 個元素,我們想找到一個給定的元素 X

  • lo0mid-1hin-1
  • lo<=hi,且 X 位於 lo 和 hi 之間的範圍時,即 X >= A[lo]X <= A[hi]
    • 利用探測位置的公式計算 mid - mid = lo + (X - A[lo]) * (hi - lo) / (A[hi] - A[lo])
    • 如果探測位置的元素小於目標元素,則向右移動。如果 A[mid]<X,則設定 lomid + 1
    • 否則,如果元素大於目標元素,則向左移動。如果 A[mid]>X,則設定 himid-1
    • 否則我們已經找到了元素並返回 mid
  • 如果 lo=hi,只剩下一個元素,檢查它是否是目標元素,即如果 A[lo]==X
    • 如果 true,則返回 lo
    • 否則返回 -1

插值搜尋示例

假設我們有一個陣列 - (1, 3, 7, 8, 11, 15, 17, 18, 21),我們想找到 X - 18

  • lo=0mid=-1hi=8
  • 利用公式-0+(18-1)*(8-0)/(21-1) 計算 mid6
  • 然後我們將 A[6]X 進行比較,看其較小,設 lo7
  • 7+(18-18)*(8-7)/(21-18) 計算 mid
  • 然後我們將 A[7]X 進行比較,看是否等於 18,並返回指數 7

插值搜尋演算法的實現

#include <bits/stdc++.h>
using namespace std;

int interpolation_search(int arr[], int n, int X)
{
    int lo = 0;
    int hi = n - 1;
    int mid;

    while ((arr[hi] != arr[lo]) && (X >= arr[lo]) && (X <= arr[hi])) {
        mid = lo + ((X - arr[lo]) * (hi - lo) / (arr[hi] - arr[lo]));

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

    if (X == arr[lo])
        return lo ;
    else
        return -1;
}

int main(void)
{
    int n = 9;
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x = 4;
    int result = interpolation_search(arr, n, x);
    if (result == -1) {
        cout << "Element not found !!";
    }
    else cout << "Element found at index " << result;
    return 0;
}

插值搜尋演算法的複雜度

時間複雜度

  • 平均情況

該演算法的平均時間複雜度為 O(log(logn))。當陣列內的所有元素都均勻分佈時,就會出現這種情況。

  • 最佳情況

當我們要搜尋的元素是插值搜尋所探查的第一個元素時,就會出現最佳情況。最佳情況下演算法的時間複雜度是 O(1)

  • 最壞情況

最壞的情況發生在目標的數值成倍增加的時候。最壞情況下演算法的時間複雜度為 O(n)

空間複雜度

這種演算法的空間複雜度是 O(1),因為除了臨時變數外,它不需要任何資料結構。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Search Algorithm