插值搜尋
插值搜尋是一種快速高效的搜尋演算法。它改進了二叉搜尋演算法，適用於陣列元素均勻分佈在排序陣列上的場景。它的工作原理是探測所需值的位置。與二叉搜尋不同的是，它並不總是去陣列的中間，而是可能根據要搜尋的鍵值去任何位置。我們比較估計位置的值，並將搜尋空間縮小到它之後或之前的部分。例如，當我們在字典中搜尋一個單詞時，我們根據裡面字母的位置來翻頁，而不是每次都把搜尋空間分成兩半。
插值搜尋演算法
假設我們有一個未排序的陣列 A[]，包含 n 個元素，我們想找到一個給定的元素 X。
-
設
lo為0，mid為-1，hi為n-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，則設定lo為mid + 1。 - 否則，如果元素大於目標元素，則向左移動。如果
A[mid]>X，則設定hi為mid-1。 - 否則我們已經找到了元素並返回
mid。
- 利用探測位置的公式計算
-
如果
lo=hi，只剩下一個元素，檢查它是否是目標元素，即如果A[lo]==X。- 如果
true，則返回lo。 - 否則返回
-1。
- 如果
插值搜尋示例
假設我們有一個陣列 - (1, 3, 7, 8, 11, 15, 17, 18, 21)，我們想找到 X - 18。
-
設
lo=0，mid=-1，hi=8。 -
利用公式-
0+(18-1)*(8-0)/(21-1)計算mid為6。 -
然後我們將
A[6]與X進行比較，看其較小，設lo為7。 -
用
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 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