插值查找

插值查找是对二分查找的一种改进，适用于均匀分布的有序表

代码基本上和二分查找一样，有修改的地方就是mid的获取
在二分查找中，

image.png
我们做一些简单的数学变换就变成:
image.png

也就是说我们的mid每次都是折中的取，但是对于一些均匀分布的有序表，这样做感觉有些费时，比如找字典的时候，找a这个字母，我们肯定不会从中间开始，而是偏向于字典前面一些开始。
插值查找就是基于这样的思想
我们对1/2进行改进:

image.png

• key就是要查找的值
• 数组a是有序表

简单的理解就是计算出key所占比，然后更好地找到key所在的区间范围
但是对于极端分布的数组，插值查找的效率就大打折扣了
比如
a[7]={0,1,2,100,102,1000,10000}

代码实现 c++

//这里是用递归实现的，其实只要对传统利用循环的二分查找做一个修改即可
int InsertionSearch(int a[], int value, int low, int high)
{
    if(low>high)
    return -1; 
    int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
    if(a[mid]==value)
        return mid;
    if(a[mid]>value)
        return InsertionSearch(a, value, low, mid-1);
    if(a[mid]<value)
        return InsertionSearch(a, value, mid+1, high);
}