Data Structures Algorithms 简明教程

Fibonacci Search Algorithm

顾名思义，斐波那契搜索算法使用斐波那契数来搜索已排序输入数组中的元素。

As the name suggests, the Fibonacci Search Algorithm uses Fibonacci numbers to search for an element in a sorted input array.

但首先，让我们回顾一下我们对斐波那契数的了解−

But first, let us revise our knowledge on Fibonacci numbers −

斐波那契数列是一个数字序列，有两个基本数 0 和 1。后续数字是该序列中前两个数字的和。这是一个无限常数序列，因此，其中的数字是固定的。斐波那契数列中的前几个数字包括−

Fibonacci Series is a series of numbers that have two primitive numbers 0 and 1. The successive numbers are the sum of preceding two numbers in the series. This is an infinite constant series, therefore, the numbers in it are fixed. The first few numbers in this Fibonacci series include −

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…

斐波那契数列背后的主要思想也是消除可能找到元素的最少位置。在某种程度上，它类似于分治算法（其逻辑最接近二分查找算法）。与跃查找和指数查找一样，此算法还会跳过输入数组的索引以执行搜索。

The main idea behind the Fibonacci series is also to eliminate the least possible places where the element could be found. In a way, it acts like a divide & conquer algorithm (logic being the closest to binary search algorithm). This algorithm, like jump search and exponential search, also skips through the indices of the input array in order to perform searching.

Fibonacci Search Algorithm

斐波那契搜索算法利用斐波那契数列来减小执行搜索的数组的范围。每次迭代，搜索范围都会减小，从而更容易在数组中找到元素。下面将详细介绍搜索过程−

The Fibonacci Search Algorithm makes use of the Fibonacci Series to diminish the range of an array on which the searching is set to be performed. With every iteration, the search range decreases making it easier to locate the element in the array. The detailed procedure of the searching is seen below −

*步骤 1 *− 作为第一步，找到大于或等于输入数组大小的斐波那契数。然后，还保留选定斐波那契数的前两个数字，也就是说，我们从斐波那契序列中保留 Fm、Fm-1、Fm-2 数字。

*Step 1 *− As the first step, find the immediate Fibonacci number that is greater than or equal to the size of the input array. Then, also hold the two preceding numbers of the selected Fibonacci number, that is, we hold Fm, Fm-1, Fm-2 numbers from the Fibonacci Series.

*步骤 2 *− 将偏移值初始化为 -1，因为最初我们将整个数组视为搜索范围。

*Step 2 *− Initialize the offset value as -1, as we are considering the entire array as the searching range in the beginning.

*步骤 3 *− 在 Fm-2 大于 0 之前，我们执行以下步骤−

*Step 3 *− Until Fm-2 is greater than 0, we perform the following steps −

Compare the key element to be found with the element at index [min(offset+Fm-2,n-1)]. If a match is found, return the index.
If the key element is found to be lesser value than this element, we reduce the range of the input from 0 to the index of this element. The Fibonacci numbers are also updated with Fm = Fm-2.
But if the key element is greater than the element at this index, we remove the elements before this element from the search range. The Fibonacci numbers are updated as Fm = Fm-1. The offset value is set to the index of this element.

Step 4 − 由于斐波那契数列中有两个 1，因此会出现两个前继数字变为 1 的情况。因此，如果 Fm-1 变成 1，则数组中只剩一个元素要搜索。我们将关键元素与该元素进行比较并返回第 1 个索引。否则，算法返回搜索失败。

Step 4 − As there are two 1s in the Fibonacci series, there arises a case where your two preceding numbers will become 1. So if Fm-1 becomes 1, there is only one element left in the array to be searched. We compare the key element with that element and return the 1st index. Otherwise, the algorithm returns an unsuccessful search.

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;
end

Analysis

斐波那契搜索算法采用对数时间复杂度来搜索元素。由于它基于分治法并且类似于二分搜索的思想，因此在最坏情况下此算法执行所需的时间复杂度为 O(log n) 。

The Fibonacci Search algorithm takes logarithmic time complexity to search for an element. Since it is based on a divide on a conquer approach and is similar to idea of binary search, the time taken by this algorithm to be executed under the worst case consequences is O(log n).

Example

假设我们有一个元素为 {12, 14, 16, 17, 20, 24, 31, 43, 50, 62} 的已排序数组，并且需要使用斐波那契搜索来查找元素 24 的位置。

Suppose we have a sorted array of elements {12, 14, 16, 17, 20, 24, 31, 43, 50, 62} and need to identify the location of element 24 in it using Fibonacci Search.

Step 1

输入数组大小为 10。大于 10 的最小斐波那契数为 13。

The size of the input array is 10. The smallest Fibonacci number greater than 10 is 13.

因此，Fm = 13，Fm-1 = 8，Fm-2 = 5。

Therefore, Fm = 13, Fm-1 = 8, Fm-2 = 5.

我们初始化偏移量 = -1

We initialize offset = -1

Step 2

在第一次迭代中，将其与位于索引 = 最小值（偏移量 + Fm-2，n – 1）的元素 = 最小值（-1 + 5，9）= 最小值（4，9）= 4 进行比较。

In the first iteration, compare it with the element at index = minimum (offset + Fm-2, n – 1) = minimum (-1 + 5, 9) = minimum (4, 9) = 4.

数组中的第四个元素为 20，它不匹配且小于关键字元素。

The fourth element in the array is 20, which is not a match and is less than the key element.

Step 3

在第二次迭代中，更新偏移量值和斐波那契数。

In the second iteration, update the offset value and the Fibonacci numbers.

由于关键字较大，偏移量值将变为元素索引，即 4。斐波那契数更新为 Fm = Fm-1 = 8。

Since the key is greater, the offset value will become the index of the element, i.e. 4. Fibonacci numbers are updated as Fm = Fm-1 = 8.

Fm-1 = 5，Fm-2 = 3。

Fm-1 = 5, Fm-2 = 3.

现在，将其与位于索引 = 最小值（偏移量 + Fm-2，n – 1）= 最小值（4 + 3，9）= 最小值（7，9）= 7 的元素进行比较。

Now, compare it with the element at index = minimum (offset + Fm-2, n – 1) = minimum (4 + 3, 9) = minimum (7, 9) = 7.

数组中第 7 个索引处的元素为 43，它不匹配且也小于关键字。

Element at the 7th index of the array is 43, which is not a match and is also lesser than the key.

Step 4

我们丢弃第 7 个索引之后的元素，所以 n = 7 和偏移量值仍为 4。

We discard the elements after the 7th index, so n = 7 and offset value remains 4.

斐波那契数向后移动两步，即 Fm = Fm-2 = 3。

Fibonacci numbers are pushed two steps backward, i.e. Fm = Fm-2 = 3.

Fm-1 = 2，Fm-2 = 1。

Fm-1 = 2, Fm-2 = 1.

现在，将其与位于索引 = 最小值（偏移量 + Fm-2，n – 1）= 最小值（4 + 1，6）= 最小值（5，7）= 5 的元素进行比较。

Now, compare it with the element at index = minimum (offset + Fm-2, n – 1) = minimum (4 + 1, 6) = minimum (5, 7) = 5.

数组中第 5 个索引处的元素为 24，这是我们的关键字元素。第 5 个索引作为此示例数组的输出被返回。

The element at index 5 in the array is 24, which is our key element. 5th index is returned as the output for this example array.

输出显示为 5。

The output is returned as 5.

Implementation

斐波那契搜索算法使用分而治之策略来消除不太可能包含所需元素的搜索空间。该消除操作借助斐波那契数来缩小输入数组中的搜索范围。下面展示了用四种不同编程语言实现的斐波那契搜索方法：

The Fibonacci search algorithm uses the divide and conquer strategy to eliminate the search spaces that are not likely to contain the required element. This elimination is done with the help of the Fibonacci numbers to narrow down the search range within an input array. The implementation for the Fibonacci search method in four different programming languages is shown below −