斐波那契搜索

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