斐波那契查找算法在大学计算机基础中的应用

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

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

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

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

斐波那契数列如下所示：

斐波那契查找原理与前两种相似，仅仅改变了中间节点（mid）的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F（k-1）-1（F代表斐波那契数列），如图9-48所示所示：(www.xing528.com)

图9-48　斐波那契查找

对F（k-1）-1的理解：

由斐波那契数列F［k］=F［k-1］+F［k-2］的性质，可以得到（F［k］-1）=（F［k-1］-1）+（F［k-2］-1）+1。该式说明：只要顺序表的长度为F［k］-1，则可以将该表分成长度为F［k-1］-1和F［k-2］-1的两段，即如上图所示。从而中间位置为mid=low+F（k-1）-1类似的，每一子段也可以用相同的方式分割。

算法分析：斐波那契查找的整体时间复杂度也为O（log n）。但就平均性能，要优于二分查找。