经典算法系列之（四）：七大查找——插值查找

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。

 一.什么是插值查找？

        插值查找，有序表的一种查找方式。插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法。插值查找基于二分查找，将查找点的选择改进为自适应选择，提高查找效率。

插值查找是在二分查找的基础上进行的改进，二分查找每次将查找的范围缩小一半，即

mid=(low+high) / 2
可以看出，折半查找是一种机械式的查找方式，不是自适应的。因此， 在数值分布相对均匀的查找表中， 我们将计算mid的方式改为自适应的查找，即
mid=low+(key-a[low])/(a[high]-a[low])*(high-low)
能够有效提高查找的效率

二.基本思想

        查找( Search)是指从一批记录中找出满足指定条件的某一记录的过程，查找又称为检索。查找算法广泛应用于各类应用程序中。因此，一个有效的查找算法往往可以大大提高程序的执行效率。在实际应用中，数据的类型千变万化，每条数据项往往包含多个数据域。但是，在执行查找操作时，往往只是指定一个或几个域的值，这些作为查找条件的域称为关键字(Key)，关键字分为两类。
        我们遇到的大部分查找问题都是以主关键字为准的。而且为了方便读者的理解，后面将以整型数据关键字为例进行讲解，其他类型的关键字的查找算法与此类似。如果查找到相应的数据项，往往需要返回该数据项的地址或者位置信息。这样程序中即可通过位置信息来进行显示数据项、插入数据项、删除数据项等操作。如果没有查找到相应的数据项，则可以返回相应的提示信息。
        在实际应用中，针对不同的情况往往可以选择不同的查找算法。对于无顺序的数据，只有逐个比较数据，才能找到需要的内容，这种方法称为顺序查找。对于有顺序的数据，也可以采用顺序查找法逐个比较，但也可以采取其他更快速的方法找到所需数据。另外，对于一些特殊的数据结构，例如链表、树结构和图结构等，也都有相对应的合适的查找算法。
插值类似于平常查英文字典的方法，在查一个以字母C开头的英文单词时，决不会用二分查找，从字典的中间一页开始，因为知道它的大概位置是在字典的较前面的部分，因此可以从前面的某处查起，这就是插值查找的基本思想。
插值查找除要求查找表是顺序存储的有序表外，还要求数据元素的关键字在查找表中均匀分布，这样，就可以按比例插值。 

三.算法复杂度分析

         插值查找性能分析：算法在最好和最坏情况下的关键字比较次数是明显的，但平均情况的分析比较复杂，并且这里的“平均”与前面讨论过的查找算法的平均不同，这里是在元素满足某种分布情况下的平均。

四.性能分析

        适合用于关键字值分布均匀的集合。 根据关键字的分布估计被查元素的位置，能更精确定位到被查找元素的位置，但应用有限。

五.代码例子

        

int func(int arr[], int len, int key)
{
int low,high,mid;
low = 0;
high = len-1;
int h = (key-arr[low])/(arr[high]-arr[low]);
while(low <= high)
{
mid = h * (high - low);
if(key < arr[mid])
{
high = mid - 1;
}
else if(key > arr[mid])
{
low = mid + 1;
}
else
{
return mid;
}
}
return -1;
}