什麼是一費搜尋法，或是稱為費式搜尋法

Question

如題
請說明費式搜尋法的過程，
因為不懂，所以希望大家能幫幫忙

Answer 1

費式搜尋法 ( fibonacci search )

特性
　　費式搜尋觀念與二元搜尋相似，只是二元搜尋每次一分為二，而每費式搜尋是依據費式數列來
　　劃分的。

定義
　　Fi = F<sub>i-1 + Fi-2 ，i >= 0 ; F0 = 0 , F1 = 1
　　由上式公式可得費式數列：0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , ....

作法
　　假設有 n 個記錄 ( record ) ，此數目比某一費式數目少 1 ，即 n = Fk-1。然後第一次比較的鍵值
　　是 KFk-1。當
　　(１) K < KFk-1 ：所有找的鍵值落在 1 至 Fk-1 - 1 之間。
　　(２) K = KFk-1 ：表示找到了。
　　(３) K ＞KFk-1 ：所要找的鍵值落在 Fk-1 + 1 至 Fk-1 之間。
比較
　　觀念上類似二分搜尋法，不是每次一分為二，而是根據某一個費氏級數來分割的。在平均的狀
　　況，它的平均搜尋次數少於二分搜尋法，但最壞的狀況則多於二分搜尋法。其平均比較次數接
　　近於 log 2 N 。
　　時間複雜度 ( time complexity ) 是 O ( log 2 N ) 。</sub>