HeIp瞭解斐波納契搜索

Question

在互聯網上，我只找到算法的代碼，但我需要首先理解文本的形式，因爲我只能從代碼中理解事情。對於我來說算法的其他描述非常複雜（在維基百科和其他網站上）。

這裏是我的理解遠：

讓我們說，我們要在數組中的元素10搜索：

Index i 0 1 2 3 4 
     2 3 4 10 40 

一些斐波那契數在這裏：我們做

Index j 0 1 2 3 4 5 6 7 8 9 
     0 1 1 2 3 5 8 13 21 34 

第一件事是發現斐波納契數大於數組長度。數組長度爲4，所以我們需要取指數位置j=5的斐波納契數字5。

但我們現在劃分數組的位置以及如何繼續？我真的不理解它..請幫忙理解考試...

Answer 1

該算法採取以下方式： 數組的長度是5，所以大於或等於5的斐波那契數是5.斐波納契數列中的前兩個數是2 [n-2]和3 [n-1] - （2,3,5）。

所以，ARR [N-2]即ARR [2]與作爲10.

如果元素比數時，則該序列被移位1周時間要搜索的數目進行比較左邊。此外，前一個索引將保存在下一個迭代中，以便爲該索引提供偏移量。在這種情況下，因爲4較小，所以n-2變爲1（1,2,3）。 arr [1 + 2（prev）] = arr [3] = 10.所以，索引號是3.

如果元素較大，序列向左移動2次。

始終將min（n-2 + offset，n）個元素與數字進行比較以獲得匹配結果。