斐波那契查找算法

Table of content
上一页
下一页

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

但首先，让我们回顾一下斐波那契数的知识——

斐波那契数列是一系列数字，有两个原始数字 0 和 1。后续数字是数列中前两个数字的和。这是一个无限常数数列，因此其中的数字是固定的。斐波那契数列的前几个数字包括——

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

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

斐波那契查找算法

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

步骤 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。偏移值设置为此元素的索引。

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

伪代码

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

分析

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

示例

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

searching_for_24

步骤 1

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

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

我们将偏移值初始化为 -1

步骤 2

在第一次迭代中，将其与索引 = min (offset + Fm-2, n – 1) = min (-1 + 5, 9) = min (4, 9) = 4 处的元素进行比较。

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

fourth_element_array_20

步骤 3

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

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

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

现在，将其与索引 = min (offset + Fm-2, n – 1) = min (4 + 3, 9) = min (7, 9) = 7 处的元素进行比较。

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

7th_index

步骤 4

我们丢弃第 7 个索引之后的元素，因此 n = 7，偏移值保持为 4。

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

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

现在，将其与索引 = min (offset + Fm-2, n – 1) = min (4 + 1, 6) = min (5, 7) = 5 处的元素进行比较。

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

index_5th

输出返回为 5。

实现

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

C C++ Java Python
#include <stdio.h>
int min(int, int);
int fibonacci_search(int[], int, int);
int min(int a, int b){
    return (a > b) ? b : a;
}
int fibonacci_search(int arr[], int n, int key){
    int offset = -1;
    int Fm2 = 0;
    int Fm1 = 1;
    int Fm = Fm2 + Fm1;
    while (Fm < n) {
        Fm2 = Fm1;
        Fm1 = Fm;
        Fm = Fm2 + Fm1;
    }
    while (Fm > 1) {
        int i = min(offset + Fm2, n - 1);
        if (arr[i] < key) {
            Fm = Fm1;
            Fm1 = Fm2;
            Fm2 = Fm - Fm1;
            offset = i;
        } else if (arr[i] > key) {
            Fm = Fm2;
            Fm1 = Fm1 - Fm2;
            Fm2 = Fm - Fm1;
        } else
            return i;
    }
    if (Fm1 && arr[offset + 1] == key)
        return offset + 1;
    return -1;
}
int main(){
   int i, n, key, pos;
   int arr[10] = {6, 11, 19, 24, 33, 54, 67, 81, 94, 99};
   printf("Array elements are: ");
   int len = sizeof(arr) / sizeof(arr[0]);
   for(int j = 0; j<len; j++){
      printf("%d ", arr[j]);
   }
   n = 10;
   key = 67;
   printf("\nThe element to be searched: %d", key); 
   pos = fibonacci_search(arr, n, key);
    if(pos >= 0)
        printf("\nThe element is found at index %d", pos);
    else
        printf("\nUnsuccessful Search");
}

输出

Array elements are: 6 11 19 24 33 54 67 81 94 99 
The element to be searched: 67
The element is found at index 6

#include <iostream>
using namespace std;
int min(int, int);
int fibonacci_search(int[], int, int);
int min(int a, int b){
   return (a > b) ? b : a;
}
int fibonacci_search(int arr[], int n, int key){
   int offset = -1;
   int Fm2 = 0;
   int Fm1 = 1;
   int Fm = Fm2 + Fm1;
   while (Fm < n) {
      Fm2 = Fm1;
      Fm1 = Fm;
      Fm = Fm2 + Fm1;
   }
   while (Fm > 1) {
      int i = min(offset + Fm2, n - 1);
      if (arr[i] < key) {
         Fm = Fm1;
         Fm1 = Fm2;
         Fm2 = Fm - Fm1;
         offset = i;
      } else if (arr[i] > key) {
         Fm = Fm2;
         Fm1 = Fm1 - Fm2;
         Fm2 = Fm - Fm1;
      } else
         return i;
   }
   if (Fm1 && arr[offset + 1] == key)
      return offset + 1;
   return -1;
}
int main(){
   int i, n, key, pos;
   int arr[10] = {6, 11, 19, 24, 33, 54, 67, 81, 94, 99};
   cout<<"Array elements are: ";
   for(auto j : arr){
      cout<<j<<" ";
   }
   n = 10;
   key = 67;
   cout<<"\nThe element to be searched: "<<key;
   pos = fibonacci_search(arr, n, key);
   if(pos >= 0)
      cout << "\nThe element is found at index " << pos;
   else
      cout << "\nUnsuccessful Search";
}

输出

Array elements are: 6 11 19 24 33 54 67 81 94 99 
The element to be searched: 67
The element is found at index 6

import java.io.*;
import java.util.Scanner;
public class FibonacciSearch {
   static int min(int a, int b) {
      return (a > b) ? b : a;
   }
   static int fibonacci_search(int arr[], int n, int key) {
      int offset = -1;
      int Fm2 = 0;
      int Fm1 = 1;
      int Fm = Fm2 + Fm1;
      while (Fm < n) {
         Fm2 = Fm1;
         Fm1 = Fm;
         Fm = Fm2 + Fm1;
      }
      while (Fm > 1) {
         int i = min(offset + Fm2, n - 1);
         if (arr[i] < key) {
            Fm = Fm1;
            Fm1 = Fm2;
            Fm2 = Fm - Fm1;
            offset = i;
        } else if (arr[i] > key) {
            Fm = Fm2;
            Fm1 = Fm1 - Fm2;
            Fm2 = Fm - Fm1;
        } else
          return i;
      }
      if (Fm1 == 1 && arr[offset + 1] == key)
         return offset + 1;
      return -1;
   }
   public static void main(String args[]) {
      int i, n, key;
      int arr[] = {6, 11, 19, 24, 33, 54, 67, 81, 94, 99};
	  System.out.print("Array elements are: ");
	  for(int j = 0; j<arr.length; j++){
	     System.out.print(arr[j] + " ");
      }
      n = 10;
      key = 67;
	  System.out.print("\nThe element to be searched: " + key);
      int pos = fibonacci_search(arr, n, key);
      if(pos >= 0)
         System.out.print("\nThe element is found at index " + pos);
      else
         System.out.print("\nUnsuccessful Search");
   }
}

输出

Array elements are: 6 11 19 24 33 54 67 81 94 99 
The element to be searched: 67
The element is found at index 6

def fibonacci_search(arr, n, key):
   offset = -1
   Fm2 = 0
   Fm1 = 1
   Fm = Fm2 + Fm1
   while (Fm < n):
      Fm2 = Fm1
      Fm1 = Fm
      Fm = Fm2 + Fm1
   while (Fm > 1):
      i = min(offset + Fm2, n - 1)
      if (arr[i] < key):
         Fm = Fm1
         Fm1 = Fm2
         Fm2 = Fm - Fm1
         offset = i
      elif (arr[i] > key):
         Fm = Fm2
         Fm1 = Fm1 - Fm2
         Fm2 = Fm - Fm1
      else:
         return i
   if (Fm1 == 1 and arr[offset + 1] == key):
      return offset + 1
   return -1
arr = [12, 14, 16, 17, 20, 24, 31, 43, 50, 62]
print("Array elements are: ")
for j in range(len(arr)):
   print(arr[j], end = " ")
n = len(arr);
key = 20
print("\nThe element to be searched:", key)
index = fibonacci_search(arr, n, key)
if(index >= 0):
   print("The element is found at index: ", (index))
else:
   print("Unsuccessful Search")

输出

Array elements are: 
12 14 16 17 20 24 31 43 50 62 
The element to be searched: 20
The element is found at index:  4
打印页面
上一页
下一页
广告