常用的7大查找算法之三:插值查找算法(自适应有序)

2017-04-23 17:33 阅读 778 次 评论 0 条

1.查找算法概述

查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法,说是七种,其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。

 

(1)查找定义

根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。

 

(2)查找算法分类

1)静态查找和动态查找

注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。

2)无序查找和有序查找

无序查找:被查找数列有序无序均可;

有序查找:被查找数列必须为有序数列。

 

(3)查找算法分析

平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。

对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = Pi*Ci的和。

Pi:查找表中第i个数据元素的概率。

Ci:找到第i个数据元素时已经比较过的次数。

 

2.插值查找

(1)插值查找说明

在介绍插值查找之前,首先考虑一个新问题,为什么上述算法一定要是折半,而不是折四分之一或者折更多呢?

打个比方,在英文字典里面查“apple”,你下意识翻开字典是翻前面的书页还是后面的书页呢?如果再让你查“zoo”,你又怎么查?很显然,这里你绝对不会是从中间开始查起,而是有一定目的的往前或往后翻。

同样的,比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5, 我们自然会考虑从数组下标较小的开始查找。

经过以上分析,折半查找这种查找方式,不是自适应的(也就是说是傻瓜式的)。二分查找中查找点计算如下:

mid=(low+high)/2, 即mid=low+1/2*(high-low);

通过类比,我们可以将查找的点改进为如下:

mid=low+(key-a[low])/(a[high]-a[low])*(high-low),

也就是将上述的比例参数1/2改进为自适应的,根据关键字在整个有序表中所处的位置,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。

 

(2)基本思想

基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,插值查找也属于有序查找。

注:对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。

 

(3)复杂度分析

查找成功或者失败的时间复杂度均为O(log2(log2n))。

 

(4)插值查找C语言源代码

(5)插值查找C++语言源代码

 

 

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用的7大查找算法之三:插值查找算法(自适应有序) | 算法君

发表评论


表情