【概述】

斐波那契查找，其利用了黃金分割原理來對二分查找進行了改進。

黃金分割又稱黃金比例，是指事物各部分間一定的數(shù)學(xué)比例關(guān)系，即將整體一分為二，較大部分與較小部分之比等于整體與較大部分之比，其比值約為 1:0.618 或 1.618:1，黃金比例不僅在繪畫、藝術(shù)上有著重要的審美價值，在工程上也具有極大的作用。

在二分查找中，每次查找都是將查找表一分為二，無論數(shù)據(jù)是偏大還是偏小，很多時候都未必是最合適的做法，而對于斐波那契數(shù)列，其從第三個數(shù)開始，前后兩個數(shù)的比值會越來越接近 0.618，利用這個特性，可對二分查找進行改進。

【基本思想】

斐波那契查找中，首先根據(jù)查找表的長度 n 來計算 n 位于斐波那契數(shù)列的位置 k，然后根據(jù) F[k] 來將查找表中不滿的數(shù)值補全，再利用位置 k 來計算查找點 mid

即：mid=low+F[k-1]-1

此后，將 a[mid] 與 key 值進行比較，根據(jù)比較結(jié)果來調(diào)整查找區(qū)間：

• 當(dāng) key<a[mid] 時：查找記錄小于當(dāng)前查找點，最高下標(biāo)調(diào)整到 mid-1 處，斐波那契數(shù)列下標(biāo) k 相應(yīng) -1
• 當(dāng) key>a[mid] 時：查找記錄大于當(dāng)前查找點，最低下標(biāo)調(diào)整到 mid+1 處，斐波那契數(shù)列下標(biāo) k 相應(yīng) -2
• 當(dāng) key=a[mid] 時：說明查找成功，此時要與 n 進行比較，來判斷是查找到的位置還是補全的數(shù)值，當(dāng) mid<=n 時，說明查找成功，返回 mid；反之，查找到的是補全數(shù)值，返回 n

【源程序】

int F[N]; void Fibonacci(){//構(gòu)造斐波那契數(shù)列F[0]=0;F[1]=1;for(int i=2;i<N;++i)F[i]=F[i-1]+F[i-2]; } int fibonacciSearch(int a[],int n,int key){int low=0;int high=n;Fibonacci();//構(gòu)造斐波那契數(shù)列int k=0;while(n>F[k]-1)//計算n位于斐波那契數(shù)列的位置k++;for(int i=n;i<F[k]-1;i++)//將數(shù)組a擴展到F[k]-1的長度a[i]=a[n];while(low<=high){int mid=low+F[k-1]-1;if(key<temp[mid]){//查找記錄小于當(dāng)前查找點high=mid-1;k--;//斐波那契數(shù)列下標(biāo)-1}else if(key>temp[mid]){//查找記錄大于當(dāng)前查找點low=mid+1;k-=2;//斐波那契數(shù)列下標(biāo)-2}else{if(mid<=n)//mid即為查找到的位置return mid; else//是擴展的數(shù)值return n;}} return -1;//查找失敗 }

總結(jié)

以上是生活随笔為你收集整理的理论基础 —— 查找 —— 斐波那契查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。