斐波那契搜尋
斐波那契搜尋是一種高效的區間搜尋演算法。它與二叉搜尋類似，也是基於分而治之的策略，也需要對陣列進行排序。此外，這兩種演算法的時間複雜度都是對數的。之所以稱為斐波那契搜尋，是因為它利用了斐波那契數列(當前數是兩個前級數之和 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時，執行以下操作。- 將
X與fib(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)=8，fib(m-1)=5，fib(m-2)=3。 -
第一次迭代
- 我們計算元素的索引為 min(
-1+3,6)，得到元素為A[2]=3。 3<6即A[2]<X因此我們捨棄A[0.... 2]，設定offset為2。- 我們還更新斐波那契序列，將
fib(m-2)移到2，fib(m-1)移到3，fib(m)移到5。
- 我們計算元素的索引為 min(
-
第二次迭代
- 我們計算元素的索引為
min(2 + 2, 6)，得到元素為A[4] = 5。 5<6即A[4]<X因此我們捨棄A[2 .... 4]，設定offset為4。- 我們還更新斐波那契序列，將
fib(m-2)移到1，fib(m-1)移到2，fib(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 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