插值搜索
Harshit Jindal
2023年10月12日
插值搜索是一种快速高效的搜索算法。它改进了二叉搜索算法，适用于数组元素均匀分布在排序数组上的场景。它的工作原理是探测所需值的位置。与二叉搜索不同的是，它并不总是去数组的中间，而是可能根据要搜索的键值去任何位置。我们比较估计位置的值，并将搜索空间缩小到它之后或之前的部分。例如，当我们在字典中搜索一个单词时，我们根据里面字母的位置来翻页，而不是每次都把搜索空间分成两半。
插值搜索算法
假设我们有一个未排序的数组 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
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