斐波那契查詢演算法

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
列印頁面
上一頁
下一頁
廣告