內(nèi)容來自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會偶爾插入自己的注釋和理解，盡量會完成作業(yè)

這次內(nèi)容有點難理解，第一次聽不懂沒關(guān)系，可以拿出紙筆跟著寫一遍

8.5斐波那契(黃金分割)查找算法

8.5.1斐波那契(黃金分割法)查找基本介紹

黃金分割點是指把一條線段分割為兩部分，使其中一部分與全長之比等于另一部分與這部分之比。取其前三位數(shù)字的近似值是0.618。由于按此比例設(shè)計的造型十分美麗，因此稱為黃金分割，也稱為中外比。這是一個神奇的數(shù)字，會帶來意想不到的效果。

斐波那契數(shù)列{1,1,2,3,5,8,13,21,34,55 }發(fā)現(xiàn)斐波那契數(shù)列的兩個相鄰數(shù)的比例,無限接近黃金分割值0.618

8.5.2斐波那契(黃金分割法)原理

斐波那契查找原理與前兩種相似，僅僅改變了中間結(jié)點(mid)的位置，mid不再是中間或插值得到,而是位于黃金分割點附近，即mid=low+F(k-1)-1(F代表斐波那契數(shù)列），如下圖所示

對F(k-1)-1的理解

1.????? 由斐波那契數(shù)列F[K]=F[k-1]+F[k-2]的性質(zhì)，可以得到（F[k]-1)=(F[k-1]-1)＋(F[k-2]1)+1。該式說明:只要順序表的長度為F[k]-1，則可以將該表分成長度為F[k-1]-1和F[k-2]-1的兩段，即如上圖所示。從而中間位置為

2.????? mid=low+F(k-1)-1

3.????? 類似的，每一子段也可以用相同的方式分割,但順序表長度n不一定剛好等于F[k]-1,所以需要將原來的順序表長度n增加至F[K]-1.這里的k值只要能使得F[好]-1恰好大于或等于n即可，由以下代碼得到,順序表長度增加后，新增的位置（從n1到F[k]-1位置)，都賦為n位置的值即可。

while(n>fib(k)-1)

k++

8.5.3斐波那契(黃金分割法)查找應(yīng)用案例

請對一個有序數(shù)組進(jìn)行斐波那契查找{1,8,10,89,1000,1234}，輸入一個數(shù)看看該數(shù)組是否存在此數(shù)，并且求出下標(biāo)，如果沒有就提示"沒有這個數(shù)"。

代碼實現(xiàn)

確實有點難理解，建議拿出紙筆，跟著寫一遍，或者debug一遍