插值搜索
对于二分搜索技术，列表被分成相等的部分。对于插值搜索技术，程序将尝试使用插值公式来定位准确位置。找到估计位置后，它可以使用该位置分隔列表。由于它每次都试图找到确切的位置，因此搜索时间减少了。如果项目均匀分布，这种技术可以很容易地找到项目。
插值搜索技术的复杂性
时间复杂度：O(log2(log2n))对于平均情况和O(n)最坏情况（当项目呈指数分布时）
空间复杂度：O(1)
输入和输出
Input: A sorted list of data: 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 The search key 780 Output: 在以下位置找到的物品： 16
算法
interpolationSearch(array, start, end, key)
输入- 一个排序的数组，开始和结束位置，以及搜索键
输出： 密钥的位置（如果找到），否则位置错误。
Begin
while start <= end AND key >= array[start] AND key <= array[end] do
dist := key – array[start]
valRange := array[end] – array[start]
fraction := dist / valRange
indexRange := end – start
estimate := start + (fraction * indexRange)
if array[estimate] = key then
return estimate position
if array[estimate] < key then
start := estimate + 1
else
end = estimate -1
done
return invalid position
End示例
#include输出结果using namespace std; int interpolationSearch(int array[], int start, int end, int key) { int dist, valRange, indexRange, estimate; float fraction; while(start <= end && key >= array[start] && key <= array[end]) { dist = key - array[start]; valRange = array[end] - array[start]; //取值范围 fraction = dist / valRange; indexRange = end - start; estimate = start + (fraction * indexRange); //钥匙的估计位置 if(array[estimate] == key) return estimate; if(array[estimate] < key) start = estimate +1; else end = estimate - 1; } return -1; } int main() { int n, searchKey, loc; cout << "输入项目数： "; cin >> n; int arr[n]; //创建一个大小为n的数组 cout << "输入项目： " << endl; for(int i = 0; i< n; i++) { cin >> arr[i]; } cout << "输入搜索键在列表中搜索： "; cin >> searchKey; if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0) cout << "在以下位置找到的物品： " << loc << endl; else cout << "在列表中找不到项目。" << endl; }
输入项目数： 20 输入项目： 10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995 输入搜索键在列表中搜索： 780 在以下位置找到的物品： 16