给定一个由n个均匀分布的值组成的排序数组arr[]，编写一个函数来搜索数组中特定的元素x。

线性搜索需要O(n)个时间，跳转搜索需要O(√n)个时间，二分搜索需要O(log n)个时间。

插值搜索是对实例的二进制搜索的改进，其中排序数组中的值是均匀分布的。插值在已知数据点的离散集范围内构造新的数据点。二分查找总是到中间的元素进行检查。另一方面，插值搜索可以根据被搜索键的值去不同的位置。例如，如果键的值更接近最后一个元素，插值搜索可能会从结束端开始搜索。

算法公式

为了找到要搜索的位置，使用以下公式。

//公式的思想是返回更高的pos值

//当要搜索的元素接近arr[hi]时。和

//当接近arr[lo]时更小的值

有许多不同的插值方法，其中一个被称为线性插值。线性插值取(x1,y1)和(x2,y2)两个数据点，公式为:在点(x,y)处。

这个算法的工作方式是我们在字典中搜索单词。插值搜索算法改进了二分搜索算法。求值的公式是 K = data-low/high-low.。

K是一个常数，用来缩小搜索空间。在二分搜索的情况下，这个常数的值是:K=(low+high)/2.

pos的公式可以推导如下。

假设数组的元素是线性分布的。

直线一般方程:y = m*x + c。

Y是数组中的值，x是它的下标。

现在把lo hi和x的值代入方程

arr[hi] = m*hi+c ----(1)

arr[lo] = m*lo+c ----(2)

x = m*pos + c ----(3)

m = (arr[hi] - arr[lo] )/ (hi - lo)

subtracting eqxn (2) from (3)

x - arr[lo] = m * (pos - lo)

lo + (x - arr[lo])/m = pos

pos = lo + (x - arr[lo]) *(hi - lo)/(arr[hi] - arr[lo])

算法

内插搜寻算法的其余部分除了上面的分区逻辑外是相同的。

步骤1:在循环中，使用上面给出的公式计算“pos”的值。

步骤2:如果匹配，返回该项的索引，并退出。

步骤3:如果项目小于arr[pos]，计算左子数组的探测位置。否则，在右子数组中进行相同的计算。

步骤4:重复操作，直到找到匹配项或子数组归零。

下面是算法的C代码递归方法实现。

// C program to implement interpolation search
// with recursion
#include // If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
int interpolationSearch(int arr[], int lo, int hi, int x)
{int pos;// Since array is sorted, an element present// in array must be in range defined by cornerif (lo <= hi && x >= arr[lo] && x <= arr[hi]) {// Probing the position with keeping// uniform distribution in mind.pos = lo+ (((double)(hi - lo) / (arr[hi] - arr[lo]))* (x - arr[lo]));// Condition of target foundif (arr[pos] == x)return pos;// If x is larger, x is in right sub arrayif (arr[pos] < x)return interpolationSearch(arr, pos + 1, hi, x);// If x is smaller, x is in left sub arrayif (arr[pos] > x)return interpolationSearch(arr, lo, pos - 1, x);}return -1;
}// Driver Code
int main()
{// Array of items on which search will// be conducted.int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,22, 23, 24, 33, 35, 42, 47 };int n = sizeof(arr) / sizeof(arr[0]);int x = 18; // Element to be searchedint index = interpolationSearch(arr, 0, n - 1, x);// If element was foundif (index != -1)printf("Element found at index %d", index);elseprintf("Element not found.");return 0;
}

输出

Element found at index 4

下面是算法的C++代码递归方法实现。

// C++ program to implement interpolation search by using iteration approach
#include
using namespace std;int interpolationSearch(int arr[], int n, int x)
{// Find indexes of two cornersint low = 0, high = (n - 1);// Since array is sorted, an element present// in array must be in range defined by cornerwhile (low <= high && x >= arr[low] && x <= arr[high]){if (low == high){if (arr[low] == x) return low;return -1;}// Probing the position with keeping// uniform distribution in mind.int pos = low + (((double)(high - low) /(arr[high] - arr[low])) * (x - arr[low]));// Condition of target foundif (arr[pos] == x)return pos;// If x is larger, x is in upper partif (arr[pos] < x)low = pos + 1;// If x is smaller, x is in the lower partelsehigh = pos - 1;}return -1;
}// Main function
int main()
{// Array of items on whighch search will// be conducted.int arr[] = {10, 12, 13, 16, 18, 19, 20, 21,22, 23, 24, 33, 35, 42, 47};int n = sizeof(arr)/sizeof(arr[0]);int x = 18; // Element to be searchedint index = interpolationSearch(arr, n, x);// If element was foundif (index != -1)cout << "Element found at index " << index;elsecout << "Element not found.";return 0;
}
//this code contributed by Ajay Singh