迹忆客 专注技术分享

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