常用的7大查找算法之四:斐波那契查找算法(一种改进二分查找)

2017-04-23 17:45 阅读 938 次 评论 0 条

1.查找算法概述

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

 

(1)查找定义

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

 

(2)查找算法分类

1)静态查找和动态查找

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

2)无序查找和有序查找

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

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

 

(3)查找算法分析

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

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

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

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

 

2.斐波那契查找

(1)斐波那契查找说明

在介绍斐波那契查找算法之前,我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

黄金比例又称黄金分割,是指事物各部分间一定的数学比例关系,即将整体一分为二,较大部分与较小部分之比等于整体与较大部分之比,其比值约为1:0.618或1.618:1。

0.618被公认为最具有审美意义的比例数字,这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域,而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

大家记不记得斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….(从第三个数开始,后边每一个数都是前两个数的和)。然后我们会发现,随着斐波那契数列的递增,前后两个数的比值会越来越接近0.618,利用这个特性,我们就可以将黄金比例运用到查找技术中。

 

(2)基本思想

也是二分查找的一种提升算法,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。同样地,斐波那契查找也属于一种有序查找算法。

斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,及n=F(k)-1;

斐波那契查找的核心是:

1)当key=a[mid]时,查找成功;

2)当key<a[mid]时,新的查找范围是第low个到第mid-1个,此时范围个数为F[k-1] - 1个,即数组左边的长度,所以要在[low, F[k - 1] - 1]范围内查找;

3)当key>a[mid]时,新的查找范围是第mid+1个到第high个,此时范围个数为F[k-2] - 1个,即数组右边的长度,所以要在[F[k - 2] - 1]范围内查找。

 

(3)复杂度分析

最坏情况下,时间复杂度为O(log2n),且其期望复杂度也为O(log2n)。

网上都没有讲清楚,导致外行很难直接直观的理解斐波那契查找。

我认为,斐波那契的核心在于两点:

1)斐波那契是一种特殊的分割方法,和二分、插值本质上是一样的,都是分割方法;

2)利用了斐波那契数列特殊的性质,一个长度只要可以被黄金分割,那么分割后的片段仍然可以继续进行黄金分割,循环。

首先,我们构造一个完整的斐波那契数列,然后开始分,小于就取左边的分割,F变为F-1;大于就取右边的分割,F变为F-2。

很好理解,F-1 和 F-2,自己画个图就理解了,这是菲波那切数列特殊的性质。

 

(4)斐波那契查找算法C语言源代码

(5)斐波那契查找算法C++源代码

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:常用的7大查找算法之四:斐波那契查找算法(一种改进二分查找) | 算法君

发表评论


表情