迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 算法 >

斐波那契搜索

作者:迹忆客 最近更新:2023/03/20 浏览次数:

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

上一篇:二叉搜索

下一篇:跳跃搜索

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

将二叉树转换为二叉搜索树

发布时间:2023/03/20 浏览次数:159 分类:算法

本教程教大家如何将二叉树转换为二叉搜索树。二叉树是一种非线性数据结构。它被称为二叉树,因为每个节点最多有两个子节点。这些子节点被称为左子和右子。

二叉搜索树删除

发布时间:2023/03/20 浏览次数:164 分类:算法

本教程介绍了二叉搜索树的删除操作。

二叉搜索树检查

发布时间:2023/03/20 浏览次数:151 分类:算法

如何检查给定的二叉树是否是二叉搜索树。

二叉搜索树

发布时间:2023/03/20 浏览次数:105 分类:算法

本教程介绍了数据结构 Binary Search Tree。

二叉树遍历

发布时间:2023/03/20 浏览次数:202 分类:算法

本教程介绍了二叉树上的树遍历中序遍历、前序遍历和后序遍历。

循环双向链表

发布时间:2023/03/20 浏览次数:143 分类:算法

本教程介绍了循环双向链表的数据结构。

循环链接列表

发布时间:2023/03/20 浏览次数:188 分类:算法

本教程介绍了循环链接列表的数据结构。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便