算法描述
先来看一个实际问题：
我们在一本英汉字典中寻找单词“worst”，我们决不会仿照对半查找（或Fibonacci查找）那样，先查找字典中间的元素，然后查找字典四分之三处的元素等等. 事实上，我们是在所期望的地址（在字典的很靠后的地方）附近开始查找的，我们称这样的查找为插值查找。
可见，插值查找不同于前面讨论的几种查找算法，前面介绍的查找算法是基于严格比较的，即假定我们对线性表中元素的分布一无所知（或称没有启发式信息）. 然而实际中，很多查找问题所涉及的表满足某些统计的特点。
插值查找在实际使用时，一般要满足两个假设条件：
（1）每一次对数据的访问与通常的指令相比，费用都是相当昂贵的。例如，待查找的表一定是在磁盘而非内存中，因而每一次比较都要进行磁盘访问。
（2）数据不仅是已被排好序的，而且呈现均匀分布特征。
伪代码
insertValue_Search(R,n,element)
//实现给定有序均匀分布数组R中元素element的查找
//输入：数组R，数组长度n，待查找元素的位置
//有无待查找的元素
from←0 ,to←n-1 //初始化起止位置
while(from <= to)
middle ← from+(element-R[from])/(R[to]-R[from])*(to-from+0.5)//采用插值方法计算
if R[mid]=element return mid
if R[mid]>element to←mid-1
if R[mid]<element from←mid+1
return -1
具体实现
/*
* 功能：该函数用来实现插值查找算法
* 输入：查找数组search_table，数组长度n，查找元素element
* 输出：返回元素的位置
*/
int insertValue_Search(int search_table[], int n, int element)
{
int low = 0;
int high = n - 1;
while(low <= high)
{
int mid = (int)(low + (element-search_table[low])/(search_table[high]-search_table[low])*(high-low));
if(search_table[mid] == element)
{
return mid;
}
else if(search_table[mid] > element)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}//while
return -1;
}
从时间复杂度上来说，插值查找的时间复杂度也是O(logn)，但对于表长较大，而关键字分布又比较均匀的查找来说，插值算法的平均性能比折半查找要好得多。但是，如果数组中的分布类似[0,1,2,2000,2001,……,99998,99999]这种极端不均匀的数据，用插值查找未必是合适的算法。
所以说，没有最好的算法，只有针对具体情况的最合适的算法。
转载于:https://www.cnblogs.com/stemon/p/4476075.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/109466.html原文链接：https://javaforall.net
