斐波那契搜索
斐波那契搜索是一种高效的区间搜索算法。它与二叉搜索类似，也是基于分而治之的策略，也需要对数组进行排序。此外，这两种算法的时间复杂度都是对数的。之所以称为斐波那契搜索，是因为它利用了斐波那契数列(当前数是两个前级数之和 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