arrays - 帮助理解斐波那契搜索

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)个元素与number比较得到匹配结果。