Data Structures Algorithms 简明教程
Fibonacci Search Algorithm
顾名思义，斐波那契搜索算法使用斐波那契数来搜索已排序输入数组中的元素。
但首先，让我们回顾一下我们对斐波那契数的了解−
斐波那契数列是一个数字序列，有两个基本数 0 和 1。后续数字是该序列中前两个数字的和。这是一个无限常数序列，因此，其中的数字是固定的。斐波那契数列中的前几个数字包括−
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…斐波那契数列背后的主要思想也是消除可能找到元素的最少位置。在某种程度上，它类似于分治算法（其逻辑最接近二分查找算法）。与跃查找和指数查找一样，此算法还会跳过输入数组的索引以执行搜索。
Fibonacci Search Algorithm
斐波那契搜索算法利用斐波那契数列来减小执行搜索的数组的范围。每次迭代，搜索范围都会减小，从而更容易在数组中找到元素。下面将详细介绍搜索过程−
*步骤 1 *− 作为第一步，找到大于或等于输入数组大小的斐波那契数。然后，还保留选定斐波那契数的前两个数字，也就是说，我们从斐波那契序列中保留 Fm、Fm-1、Fm-2 数字。
*步骤 2 *− 将偏移值初始化为 -1，因为最初我们将整个数组视为搜索范围。
*步骤 3 *− 在 Fm-2 大于 0 之前，我们执行以下步骤−
-
将要查找的关键元素与索引 [min(offset+Fm-2,n-1)] 处的元素进行比较。如果找到了匹配项，则返回该索引。
-
如果发现关键元素比该元素的值小，我们会将输入的范围从 0 缩小到该元素的索引。斐波那契数字也使用 Fm = Fm-2 更新。
-
但如果关键元素大于该索引处的元素，我们将从搜索范围内删除该元素之前的元素。斐波那契数字更新为 Fm = Fm-1。偏移值设置为该元素的索引。
Step 4 − 由于斐波那契数列中有两个 1，因此会出现两个前继数字变为 1 的情况。因此，如果 Fm-1 变成 1，则数组中只剩一个元素要搜索。我们将关键元素与该元素进行比较并返回第 1 个索引。否则，算法返回搜索失败。
Pseudocode
Begin Fibonacci Search
n <- size of the input array
offset = -1
Fm2 := 0
Fm1 := 1
Fm := Fm2 + Fm1
while Fm < n do:
Fm2 = Fm1
Fm1 = Fm
Fm = Fm2 + Fm1
done
while fm > 1 do:
i := minimum of (offset + fm2, n – 1)
if (A[i] < x) then:
Fm := Fm1
Fm1 := Fm2
Fm2 := Fm - Fm1
offset = i
end
else if (A[i] > x) then:
Fm = Fm2
Fm1 = Fm1 - Fm2
Fm2 = Fm - Fm1
end
else
return i;
end
done
if (Fm1 and Array[offset + 1] == x) then:
return offset + 1
end
return invalid location;
endExample
假设我们有一个元素为 {12, 14, 16, 17, 20, 24, 31, 43, 50, 62} 的已排序数组，并且需要使用斐波那契搜索来查找元素 24 的位置。
Step 1
输入数组大小为 10。大于 10 的最小斐波那契数为 13。
因此，Fm = 13，Fm-1 = 8，Fm-2 = 5。
我们初始化偏移量 = -1
Step 2
在第一次迭代中，将其与位于索引 = 最小值（偏移量 + Fm-2，n – 1）的元素 = 最小值（-1 + 5，9）= 最小值（4，9）= 4 进行比较。
数组中的第四个元素为 20，它不匹配且小于关键字元素。
Step 3
在第二次迭代中，更新偏移量值和斐波那契数。
由于关键字较大，偏移量值将变为元素索引，即 4。斐波那契数更新为 Fm = Fm-1 = 8。
Fm-1 = 5，Fm-2 = 3。
现在，将其与位于索引 = 最小值（偏移量 + Fm-2，n – 1）= 最小值（4 + 3，9）= 最小值（7，9）= 7 的元素进行比较。
数组中第 7 个索引处的元素为 43，它不匹配且也小于关键字。
Step 4
我们丢弃第 7 个索引之后的元素，所以 n = 7 和偏移量值仍为 4。
斐波那契数向后移动两步，即 Fm = Fm-2 = 3。
Fm-1 = 2，Fm-2 = 1。
现在，将其与位于索引 = 最小值（偏移量 + Fm-2，n – 1）= 最小值（4 + 1，6）= 最小值（5，7）= 5 的元素进行比较。
数组中第 5 个索引处的元素为 24，这是我们的关键字元素。第 5 个索引作为此示例数组的输出被返回。
输出显示为 5。