文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

【愚公系列】2023年11月 七大查找算法(四)-斐波那契查找

一、斐波那契查找1.基本思想斐波那契查找算法的基本思想是将要查找的元素与斐波那契数列中的元素进行比较，并根据比较的结果确定下一步查找的范围。...具体来说，算法首先在斐波那契数列中找到大于或等于要查找的元素的最小数（称为斐波那契数列的查找点），然后根据该查找点将数组分为两部分，一部分是查找点左侧的元素，另一部分是查找点右侧的元素。...重复以上步骤，直到找到要查找的元素或者确定要查找的元素不在数组中。斐波那契查找算法的时间复杂度为O(log n)。2.复杂度分析斐波那契查找算法的时间复杂度为O(log n)，空间复杂度为O(1)。...在斐波那契查找算法中，先使用斐波那契数列生成器生成斐波那契数列，选取一个在斐波那契数列中的值作为分割点，将原序列划分为两部分。...具体应用场景如下：在大型数据集中进行查找时，斐波那契查找算法比二分查找算法更快。斐波那契查找算法可用于从有序数列中查找给定值的位置，这些数列可以是数组、链表、二叉搜索树或其他数据结构。

19222

斐波那契查找原理详解与实现

最近看见一个要求仅使用加法减法实现二分查找的题目，百度了一下，原来要用到一个叫做斐波那契查找的的算法。查百度，是这样说的： 斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。...他要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1;  开始将k值与第F(k-1）位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种  1）相等，mid位置的元素即为所求...Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找  3)<    ,high=mid-1,k-=1;说明:low=mid+1说明待查找的元素在[low,...mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找 ---- 大部分说明都忽略了一个条件的说明：n=F(k)-1， 表中记录的个数为某个斐波那契数小...std; const int max_size=20;//斐波那契数组的长度 /*构造一个斐波那契数组*/ void Fibonacci(int * F) {

1.8K80
您找到你想要的搜索结果了吗？
是的
没有找到

最长的斐波那契子序列的长度（难度：中等）

+2}； 给定一个严格递增的正整数数组形成序列arr，找到arr中最长的斐波那契式的子序列的长度。...回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。...我的解题思路是这样的，既然想要获取最长的斐波那契序列的长度，那么我们需要找出哪些序列是符合斐波那契数列的。...，具体逻辑如下图所示： 此时我们发现，num_a没有超过middle，并且num_a与num_b相加也没有超过max ，可以继续查找斐波那契子序列，具体逻辑如下图所示： 此时我们发现，num_a已经等于...全部更新完毕，一定要记得，如果result不等于0，则返回值是result+2，因为只要匹配到了斐波那契子序列，最短的举例就是3的长度，而我们上面逻辑中，如果找到了斐波那契子序列，result值赋值的是

19240

斐波那契查找不再迷惑

于是就有了裴波那契查找算法， 裴波那契数列最重要的一个性质是每个数都等于前两个数之和（从第三个数字开始）。...查找过程 OK，有了上面的基础我们总结下查找的过程： 根据待查找数组长度确定裴波那契数组的长度（或最大元素值） 根据1中长度创建该长度的裴波那契数组，再通过F(0)=1，F(1)=1, F(n)=F(n...-1)+F(n-2)生成裴波那契数列为数组赋值 以2中的裴波那契数组的最大值为长度创建填充数组，将原待排序数组元素拷贝到填充数组中来， 如果有剩余的未赋值元素， 用原待排序数组的最后一个元素值填充 针对填充数组进行关键字查找...不依赖数组的斐波那契查找 我百度“斐波那契查找”的时候， 一大部分基于数组实现的代码都是创建了一个长度固定为20的斐波那契数组。...， 要用的时候直接从数组里拿就可以了 这个版本： 不用数组存， 只算出来需要的最大的斐波那契数， 要用的时候“临时”计算就可以了 二分，插值和裴波纳契查找的性能比较 二分查找： 二分查找的轨迹可以用一颗判定树来表示

81011

常见动态规划类型--案例详解

定义状态： 确定问题的状态，即原问题和子问题中变化的变量。例如，在计算斐波那契数列问题中，定义状态 dpi 表示第 i 个斐波那契数。...例如，在计算斐波那契数列问题中，dpi = dpi-1 + dpi-2，即第 i 个斐波那契数等于前两个斐波那契数的和。 初始化： 初始化状态的初始值，通常是边界情况，用于保证状态转移的正确性。...例如，在计算斐波那契数列问题中，返回 dpn 即为所求的第 n 个斐波那契数。...dpi 表示第 i 个斐波那契数，通过循环计算并填充 dp 数组，最终返回 dpn 即为第 n 个斐波那契数。。...动态规划问题分类 常见类型的动态规划问题可以分为一下几类： 线性动态规划： 问题可以表示为一维数组的状态，例如斐波那契数列。 区间动态规划： 问题涉及对区间进行划分和计算，例如最长回文子序列。

48700

CC++语言的查找算法（下）

4、斐波那契查找 斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。...他要求开始表中记录的个数为某个斐波那契数小1，即n=F(k)-1; 开始将k值与第F(k-1）位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种 1）相等，mid位置的元素即为所求...mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归的应用斐波那契查找 大部分说明都忽略了一个条件的说明：n=F(k)-1， 表中记录的个数为某个斐波那契数小...std; const int max_size=20;//斐波那契数组的长度 /*构造一个斐波那契数组*/ void Fibonacci(int * F) { F[0]=0;...[max_size]; Fibonacci(F);//构造一个斐波那契数组F int k=0; while(n>F[k]-1)//计算n位于斐波那契数列的位置 ++k

53910

查找算法

查找算法 线性查找 二分查找 差值查找 斐波那契查找 鉴于在排序算法时, 搞得比较乱的情况, 导致查找不太方便....因此, 在写查找算法时, 我会将所有的东西都写在一起, 便于查找和阅读 在java中，我们常用的查找有四种: 顺序(线性)查找 二分查找/折半查找 插值查找 斐波那契查找 线性查找 思路: 如果在数组中发现满足条件的值...关键字分布不均匀的情况下，该方法不一定比折半查找要好 斐波那契查找 斐波那契(黄金分割法)查找基本介绍: 黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。...斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } 发现斐波那契数列的两个相邻数 的比例，无限接近 黄金分割值0.618 斐波那契(黄金分割法)原理: 斐波那契查找原理与前两种相似...斐波那契查找应用案例： 请对一个有序数组进行斐波那契查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数 代码实现 /

75710

数据结构与算法(二):查找算法

四、斐波那契查找(黄金分割查找) 基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。 　　...斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。...他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1; 开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种 　　1）相等，mid位置的元素即为所求...Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。 　　...说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。

39420

斐波那契查找

介绍 斐波那契查找（Fibonacci Search）又叫黄金分割查找，斐波那契查找和二分查找、插值查找也类似，数组也要是有序的。...要使用斐波那契查找，就要先构建一个斐波那契数列，斐波那契数列的长度就和原始数组保持一致即可，主要是用来获取中间索引mid。...left表示原始数组左边索引，初始的时候就是0，构建好斐波那契数组，我们要让f(k-1) - 1指向数组的最后一个索引，然后从斐波那契数组中根据mid = left + f(k-1) - 1来获取中间索引...如果这个数比要查找的数更小，那说明在原始数组的mid的左边，那就让right = mid - 1，同时k要减1，因为刚才我们是在斐波那契数列f(k)的位置获取的索引，在f(k)的前面，有f(k-1)个元素...如果这个数比要查找的数更大，就让left = mid + 1，同时k要减2，因为上面说了，斐波那契数列满足f(k) = f(k-1) + f(k-2)，在f(k)的左边，有f(k-1)个元素，右边有f(

31840

四大查找算法

在Java中，常用的查找算法有以下四种： 顺序查找； 二分查找； 插值查找； 斐波那契查找； ---- 欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新...这个mid的计算公式是大佬发明的，大家有兴趣可以用数学推导一下。 四、斐波那契查找 斐波那契查找又叫黄金分割查找，黄金分割是初中学习的内容，之后又学习了斐波那契数列。...1, 1, 2, 3, 5, 8, 13…… 这个就是斐波那契数列，相邻两个数的比值无限接近黄金分割值0.618。斐波那契查找就是利用斐波那契数列的这个特性来设计的查找算法。 1....斐波那契查找介绍： 斐波那契查找和二分查找、插值查找也类似，数组也要是有序的。不同之处还是mid的计算方法。公式为：mid = left + f(k-1) - 1。...mid； 斐波那契数列的长度就和原始数组保持一致即可； left表示原始数组左边索引，初始的时候就是0，构建好斐波那契数组，我们要让f(k-1) - 1指向数组的最后一个索引； 然后从斐波那契数组中根据

49721

剑指 Offer（C++版本）系列：剑指 Offer 10- I 斐波那契数列

03 数组中重复的数字 剑指 Offer（C++版本）系列：剑指 Offer 04 二维数组中的查找 剑指 Offer（C++版本）系列：剑指 Offer 05 替换空格 剑指 Offer（C++版本...Offer（C++版本）系列：剑指 Offer 10- I 斐波那契数列 1、题干 斐波那契数列 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。...斐波那契数列的定义如下： F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1....斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。...通过次数190,890提交次数552,092 2、递归法 算法流程： 转移方程：即对应数列定义 f(n + 1) = f(n) + f(n - 1)； 初始状态：即初始化前两个数字； 返回值：即斐波那契数列的第

34420

【算法】先生，您点的查找套餐到了（二分、插值和斐波那契查找）

查找过程 OK，有了上面的基础我们总结下查找的过程： 根据待查找数组长度确定裴波那契数组的长度（或最大元素值） 根据1中长度创建该长度的裴波那契数组，再通过F(0)=1，F(1)=1, F(n)=F(n...-1)+F(n-2)生成裴波那契数列为数组赋值 以2中的裴波那契数组的最大值为长度创建填充数组，将原待排序数组元素拷贝到填充数组中来， 如果有剩余的未赋值元素， 用原待排序数组的最后一个元素值填充 针对填充数组进行关键字查找...我百度“斐波那契查找”的时候， 一大部分基于数组实现的代码都是创建了一个长度固定为20的斐波那契数组。 而第20个斐波那契数是6765，所以这样的代码只能处理长度小于等于6765的数组。...于是就有了另一种编写斐波那契数组的方法： 不依赖数组的编码方法，请看： 不依赖数组的斐波那契查找 请点这里： 不依赖数组的斐波那契查找（C语言） 说一下这种方法和我上面介绍的方法的不同点 我上面介绍的版本...： 先把斐波那契数算出来，再全部用数组存起来， 要用的时候直接从数组里拿就可以了 这个版本： 不用数组存， 只算出来需要的最大的斐波那契数， 要用的时候“临时”计算就可以了 二分，插值和裴波纳契查找的性能比较

1K90

【愚公系列】2021年11月 C#版 数据结构与算法解析(斐波那契查找)

斐波那契查找是区间中单峰函数的搜索技术，它在二分查找的基础上根据斐波那契数列进行分割的。...在斐波那契数列找一个等于或略大于查找表中元素个数的数F[n]，如果原查找表长度不足F[n]，则补充重复最后一个元素，直到满足F[n]个元素时为止。...完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，根据值的关系确定往前或往后查找，直到找到时为止。如果一直找不到，则返回-1。...，使用数组保存中间结防止重复计算， //注意MAXSIZE为48时，斐波那契数将会溢出整型范围。...-1 return -1; } } 在最坏的情况下斐波那契查找的时间复杂度为：O(logn) 。

14820

Qz学算法-数据结构篇(查找算法--插值、斐波那契查找)

插值查找1.原理介绍插值查找算法类似于二分查找，不同的是插值查找每次从自适应id处开始查找。...，采用插值查找，速度较快.关键字分布不均匀的情况下，该方法不一定比折半查找要好斐波那契查找算法1.黄金分割原理黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。...斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数 列的两个相邻数的比例，无限接近黄金分割值0.6182.斐波那契额原理图片斐波那契查找原理与前两种相似，仅仅改变了中间结点(mid...)的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1(F代表斐波那契数列)，如下图所示3.对F(K-1)-1理解由斐波那契数列F[K]=F[k-1]+Fk-2...int mid = 0; //存放mid值 int f[] = Fib(); //获取斐波那契数列 //获取到斐波那契分割数值的下标 while

8000

数据结构——查找

，则查找成功，找到所查的记录；如果直到最后一个（或第一个）记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。..."); }else { System.out.println("你要查找的数在数组的第"+(result+1)+"个位置"); } } } 4、斐波那契查找 定义： 1.斐波那契实在二分查找基础上...，用斐波那契数列来进行分割 2.在斐波那契数列上找一个略大于查找元素表个数的值f(n) 3.将查找元素表个数扩充到f(n) 如果要补充元素用最后一个元素补充 4.完成后对f(n)个元素进行斐波那契分割,...; import org.junit.jupiter.api.Test; /* *----- 斐波那契查找------ * 1.斐波那契实在二分查找基础上，用斐波那契数列来进行分割 * 2.在斐波那契数列上找一个略大于查找元素表个数的值...f(n) * 3.将查找元素表个数扩充到f(n) 如果要补充元素用最后一个元素补充 * 4.完成后对f(n)个元素进行斐波那契分割,即分割成 前面f(n-1)个元素,后面f(n-2)个元素 * 5

41820

Qz学算法-数据结构篇(查找算法--插值、斐波那契查找)

插值查找1.原理介绍插值查找算法类似于二分查找，不同的是插值查找每次从自适应id处开始查找。...关键字分布不均匀的情况下，该方法不一定比折半查找要好 斐波那契查找算法1.黄金分割原理黄金分割点是指把一条线段分割为两部分，使其中一部分与全长之比等于另一部分与这部分之比。...斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数 列的两个相邻数的比例，无限接近黄金分割值0.6182.斐波那契额原理斐波那契查找原理与前两种相似，仅仅改变了中间结点(mid...)的位置，mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F(k-1)-1(F代表斐波那契数列)，如下图所示3.对F(K-1)-1理解由斐波那契数列F[K]=F[k-1]+Fk-2...int mid = 0; //存放mid值 int f[] = Fib(); //获取斐波那契数列 //获取到斐波那契分割数值的下标 while

12310

算法 最长的斐波那契子序列的长度

X_{i+2} 给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。...（回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。...2、dp + hash 对于长度为n的数列，需要为其构建一个n ^ 2的二维数组dp，保存其dp[raw][col]位置满足斐波那契序列的组数。...因为设置了dp[raw][col] 存放的是满足斐波那契序列的组数，然而题目是返回满足斐波那契序列的元素个数，所以元素个数会比组数多2，在返回结果时加2再返回即可。...并且最终结果小于3是无法组成满足斐波那契序列的，返回0即可。

40910

最长的斐波那契子序列的长度（动态规划）

题目 图片.png 给定一个严格递增的正整数数组形成序列，找到 A 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。...（回想一下，子序列是从原序列 A 中派生出来的，它从 A 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。...例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列） 示例 1： 输入: [1,2,3,4,5,6,7,8] 输出: 5 解释: 最长的斐波那契式子序列为：[1,2,3,5,8...示例 2： 输入: [1,3,7,11,12,14,18] 输出: 3 解释: 最长的斐波那契式子序列有： [1,11,12]，[3,11,14] 以及 [7,11,18] 。...解题 2.1 暴力解 以两个点为基准，生成斐波那契数列，在set中查找是否找到生成的数，记录最大 len 图片.png class Solution { public: int lenLongestFibSubseq

77230
点击加载更多

扫码

添加站长 进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

更多标签

活动推荐

    运营活动

    活动名称
    广告关闭

    腾讯云开发者

    扫码关注腾讯云开发者

    扫码关注腾讯云开发者

    领取腾讯云代金券

    热门产品

    热门推荐

    更多推荐

    Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

    深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

    腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287

    领券