我们很容易理解折半查找（二分查找），那么在折半查找原理的基础上我们会进一步思考，为什么一定要折半呢，而不是折四分之一，或者其他呢？比如说我们要搜索的值更接近最后一个元素，为什么还要从中间开始搜索，而不是从较后面的一部分开始搜索呢？因此研究学者们在折半查找的基础上进行了改进，以便更迅速准确的找到要搜素的目标值。

定义

插值查找是对二分查找的改进，其中排序数组中的值是均匀分布。 插值查找根据正在搜索的键的值，可以去不同的位置。插值查找也是有序表查找算法。

原理

插值查找的前提是有序数列元素的值是成线性增长的。对于大多数有序数列来说，这前提是可以成立的。我们不妨假设它就是成立的，那样，当我们知道一个要查找值的大小后。就可以根据数列线性增长的性质，求出要查找的值在数列中的大概位置。比如说在数列A[low,high]中查找key。我们key的下标为mid。由于数列线性增长，我们不难得到这个等式：

1

\frac{mid-low}{high-low}=\frac{key-A[low]}{A[high]-A[low]}

进而得出：

1

mid = low+\frac{key-A[low]}{A[high]-A[low]}*(high-low)

因此我们可求出mid的值，以它为轴点，可以极大的提高查找的收敛速度。说到这里，大家也都明白了，其实插值查找就是更准的二分查找而已。我们可以将插值查找与折半查找进行对比分析，看看插值查找的改进优化之处：

我们先将折半查找的核心公式变换得到：

1

mid = \frac{low+high}{2}=low+\frac{1}{2}(high-low)

将此公式与插值公式进行对比可发现：折半查找的公式中的$\frac{1}{2}$变成$\frac{key-A[low]}{A[high]-A[low]}$就成了插值查找的核心公式。这样的改进有什么道理呢？

纯粹从公式上分析，如果key的值和下界的值的差值$key-A[low]$相对于上下界的差值$A[high]-A[low]$占比例较大，说明key值更靠近上界，mid的值会较大；反之如果比例较小，说明关键字与下界的值差别不大，mid较小，说明我们更倾向于在下界附近来寻找key值。

通过一个简单的例子进一步说明改进之后的优势。假设A[11]={0，1，16，24，35，47，59，62，73，88，99}，则low=1，hig=10，A[low]=1，A[high]=99。如果我们要找的是key=16时，按照折半查找的原理，我们需要四次才可以得到结果（读者可以自行计算），但如果用插值查找，则$\frac{key-A[low]}{A[high]-A[low]}=\frac{16-1}{99-1}=0.153$即mid = 1 + 0.153 *（10 - 1）= 2.377，取整得到mid=2，我们只需要二次就可以查找到结果，显然大大提高了查找的效率。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include<iostream>  
using namespace std;  
int InterpolationSearch(int *A,int e,int lo,int hi)  
{  
    while(lo<hi)  
    {  
        int mi=lo+(hi-lo-1)*(e-A[lo])/(A[hi-1]-A[lo]);//获取查找轴点   
        if(mi>=10)//排除越界情况   
        {  
            return -1;  
        }  
        if(e<A[mi])  
        {  
            hi=mi;//深入左侧[lo,hi)   
        }  
        else if(e>A[mi])  
        {  
            lo=mi+1;//深入右侧[mi+1,hi)   
        }  
        else  
        {  
            return mi;//命中   
        }  
    }  
    return -1;//查找失败   
}  
int main()  
{  
    /*******插值查找测试******/  
    int a[10];  
    cout<<"测试数组：";  
    for(int i=0;i<10;i++)  
    {  
        a[i]=(float)(i);  
        cout<<a[i]<<" ";   
    }  
    cout<<endl;  
    cout<<"查找结果：" ;  
    for(int i=0;i<13;i++)  
    {  
        cout<<InterpolationSearch(a,i-1,0,10)<<" ";   
    }   
    cout<<endl;  
    /***************************/  

}

总结

插值查找比二分查找有所改进，但是其效率提高的并不明显(除非所查找的数列特别庞大，它的用处才能显现)。算法中引用了乘法和除法，增加了额外的消耗。如果所需查找的数列不大，由于每次深入都要进行乘除操作，用此算法可能得不偿失。所以，在实际应用中，该算法常常与二分查找算法联合使用，来处理较大的数据：用插值查找将数据缩小到一定范围，再用二分查找完成查询。时间复杂性：如果元素均匀分布，则O（log log n）），在最坏的情况下可能需要O（n）。
辅助空间：O（1）