设计与分析 - 斐波那契搜索

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

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

斐波那契数列是一系列具有两个原始数字 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。偏移值设置为此元素的索引。

步骤 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 在其中的位置。

搜索_for_24

步骤1

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

因此，F m = 13，F m-1 = 8，F m-2 = 5。

我们初始化offset = -1

第2步

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

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

Fourth_element_array_20

步骤3

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

由于键更大，所以偏移值将成为该元素的索引，即4。斐波那契数更新为F m = F m-1 = 8。

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

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

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

第 7 个索引

步骤4

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

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

F m-1 = 2，F m-2 = 1。

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

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

索引_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};
   n = 10;
   key = 67;
   pos = fibonacci_search(arr, n, key);
    if(pos >= 0)
        printf("The element is found at index %d", pos);
    else
        printf("Unsuccessful Search");
}

输出

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};
   n = 10;
   key = 67;
   pos = fibonacci_search(arr, n, key);
   if(pos >= 0)
      cout << "The element is found at index " << pos;
   else
      cout << "Unsuccessful Search";
}

输出

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};
      n = 10;
      key = 67;
      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");
   }
}

输出

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]
n = len(arr);
key = 20
index = fibonacci_search(arr, n, key)
if(index >= 0):
   print("The element is found at index: ", (index))
else:
   print("Unsuccessful Search")

输出

The element is found at index:  4