斐波那契搜索算法

更新于 2025/10/16 16:21:06

斐波那契搜索算法
实现

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

但首先，让我们复习一下关于斐波那契数列的知识。

斐波那契数列是由两个原始数字 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+F_m-2,n-1)] 处的元素进行比较。如果匹配，则返回索引。
如果发现关键元素的值小于此元素，我们将输入的范围从 0 缩小到此元素的索引。斐波那契数列也更新为 F_m = F_m-2。
但是，如果关键元素大于此索引处的元素，我们将此元素之前的元素从搜索范围中删除。斐波那契数列更新为 F_m = F_m-1。 offset 值设置为此元素的索引。

步骤 4 − 由于斐波那契数列中有两个 1，因此会出现前两个数字变为 1 的情况。因此，如果 F_m-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 的位置。

步骤 1

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

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

初始化偏移量 = -1

步骤 2

在第一次迭代中，将其与索引 = 最小值 (偏移量 + F_m-2, n – 1) = 最小值 (-1 + 5, 9) = 最小值 (4, 9) = 4 处的元素进行比较。

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

步骤 3

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

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

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

现在，将其与索引 = 最小值 (偏移量 + F_m-2, n – 1) = 最小值 (4 + 3, 9) = 最小值 (7, 9) = 7 的元素进行比较。

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

步骤 4

我们丢弃索引 7 之后的元素，因此 n = 7，偏移量值仍为 4。

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

F_m-1 = 2，F_m-2 = 1。

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

数组中索引 5 处的元素为 24，这是我们的关键元素。此示例数组的输出结果为第 5 个索引。

输出结果为 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("
The element to be searched: %d", key); 
   pos = fibonacci_search(arr, n, key);
    if(pos >= 0)
        printf("
The element is found at index %d", pos);
    else
        printf("
Unsuccessful 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<<"
The element to be searched: "<<key;
   pos = fibonacci_search(arr, n, key);
   if(pos >= 0)
      cout << "
The element is found at index " << pos;
   else
      cout << "
Unsuccessful 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("
The element to be searched: " + key);
      int pos = fibonacci_search(arr, n, key);
      if(pos >= 0)
         System.out.print("
The element is found at index " + pos);
      else
         System.out.print("
Unsuccessful 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("
The 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

数据结构和算法

数据结构

链接列表

堆栈 &队列

搜索算法

排序算法

图形数据结构

树数据结构

递归

分而治之

贪婪算法

动态规划

近似算法

随机算法

DSA 有用资源

斐波那契搜索算法

斐波那契搜索算法

伪代码

分析

示例

实现

输出

输出

输出

输出

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！