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）个元素与数字进行比较以获得匹配结果。