斐波那契搜尋

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 斐波那契搜尋演算法
  2. 斐波那契搜尋示例
  3. 斐波那契搜尋演算法的實現
  4. 斐波那契搜尋演算法的複雜度
斐波那契搜尋

斐波那契搜尋是一種高效的區間搜尋演算法。它與二叉搜尋類似,也是基於分而治之的策略,也需要對陣列進行排序。此外,這兩種演算法的時間複雜度都是對數的。之所以稱為斐波那契搜尋,是因為它利用了斐波那契數列(當前數是兩個前級數之和 F[i]=F[i-1]+F[i-2]F[0]=0&F[1]=1 是數列中的前兩個數。),將陣列分成大小由斐波那契數給定的兩部分。與二叉搜尋所需的除法、乘法和位移相比,它只使用加減運算,是一種計算方便的方法。

斐波那契搜尋演算法

假設我們有一個未排序的陣列 A[],包含 n 個元素,我們想找到一個元素-X

  • 找到最小的斐波那契數,剛好大於或等於陣列 n 的大小。讓這個數字是 m個斐波那契數 fib(m) 和它的前身 fib(m-1)fib(m-2)
  • 初始化偏移量為 -1
  • fib(m-2) 大於 0 時,執行以下操作。
    • Xfib(m-2) 所覆蓋的最後一個元素進行比較。它由 A[min(offset + fib(m-2), n - 1)] 給出。
    • 如果 X 等於這個元素,則返回索引。
    • 否則如果 X 小於這個元素,我們就丟棄這個元素後面的一半,將斐波那契序列向後移動兩步。同時,更新偏移量,改變搜尋空間的起始索引。這些步驟會丟棄陣列搜尋空間的後二分之一。
    • 否則如果 X 大於這個元素,我們就丟棄這個元素前面的一半,並將斐波那契序列向後移動一步。這一步丟棄陣列搜尋空間的前三分之一。
  • 如果 fib(m-1) 等於 1,我們有一個元素未被選中,將其與 X 進行比較。如果 X 等於這個元素,則返回索引。
  • 如果沒有一個元素符合,那麼返回 -1

斐波那契搜尋示例

假設我們有陣列 - (1, 2, 3, 4, 5, 6, 7)。我們必須尋找元素 X=6。

這個陣列有 7 個元素。所以,n=7。大於 n 的最小斐波那契數是 8。

  • 我們得到 fib(m)=8fib(m-1)=5fib(m-2)=3
  • 第一次迭代
    • 我們計算元素的索引為 min(-1 + 3 , 6 ),得到元素為 A[2] =3
    • 3 <6A[2] < X 因此我們捨棄 A[0.... 2],設定 offset2
    • 我們還更新斐波那契序列,將 fib(m-2) 移到 2fib(m-1) 移到 3fib(m) 移到 5
  • 第二次迭代
    • 我們計算元素的索引為 min(2 + 2, 6),得到元素為 A[4] = 5
    • 5<6A[4]<X 因此我們捨棄 A[2 .... 4],設定 offset4
    • 我們還更新斐波那契序列,將 fib(m-2) 移到 1fib(m-1) 移到 2fib(m) 移到 3
  • 第三次迭代
    • 我們計算元素的指數為 min(4+1,6),得到元素為 A[5]=6
    • 6=6,即 A[5]=X,我們返回指數 5

斐波那契搜尋演算法的實現

#include <bits/stdc++.h>
using namespace std;

int fibonacciSearch(int A[], int x, int n)
{
    int fbM2 = 0;
    int fbM1 = 1;
    int fbM = fbM2 + fbM1;
    int offset = -1;
    while (fbM < n)
    {
        fbM2 = fbM1;
        fbM1 = fbM;
        fbM  = fbM2 + fbM1;
    }
    while (fbM > 1)
    {
        int i = min(offset + fbM2, n - 1);
        if (A[i] < x)
        {
            fbM  = fbM1;
            fbM1 = fbM2;
            fbM2 = fbM - fbM1;
            offset = i;
        }
        else if (A[i] > x)
        {
            fbM  = fbM2;
            fbM1 = fbM1 - fbM2;
            fbM2 = fbM - fbM1;
        }
        else return i;
    }
    if (fbM1 && A[offset + 1] == x)
        return offset + 1;

    return -1;
}

int main()
{
    int n = 9;
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x = 8;
    int result = fibonacciSearch(arr, x, n);
    if (result == -1) {
        cout << "Element not found !!";
    }
    else cout << "Element found at index " << result;
    return 0;
}

斐波那契搜尋演算法的複雜度

時間複雜度

  • 平均情況

我們在每一次迭代中減少三分之一/三分之二的搜尋空間,因此該演算法具有對數的複雜度。斐波那契搜尋演算法的時間複雜度為 O(logn)

  • 最佳情況

最佳情況下的時間複雜度是 O(1)。當要搜尋的元素是我們比較的第一個元素時,就會出現這種情況。

  • 最壞情況

當目標元素 X 總是存在於較大的子陣列中時,就會出現最壞的情況。最壞情況下的時間複雜度是 O(logn)。它與平均情況下的時間複雜度相同。

空間複雜度

該演算法的空間複雜度為 O(1),因為除了臨時變數外,不需要額外的空間。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Search Algorithm