李林超博客
首页
归档
留言
友链
动态
关于
归档
留言
友链
动态
关于
首页
Java
正文
数据结构和算法学习--菲波那切(黄金分割法)查找算法
Leefs
2020-02-06 PM
1584℃
0条
# 数据结构和算法学习--菲波那切(黄金分割法)查找算法 ### 一、基本介绍 (1)黄金分割点是指把一条线段分割为两部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽,因此称为黄金分割,也称为中外比。这是一个神奇的数字,会带来意向不到的效果。 (2)菲波那切数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618 ![25.菲波那切查找算法01.png][1] ### 二、菲波那切(黄金分割法)原理 菲波那切查找原理与前两种相似,仅仅改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近,即mid=low+F(k-1)-1(F代表菲波那切数列),如下图所示 ![25.菲波那切查找算法02.png][2] **对F(k-1)-1的理解:** (1)由菲波那切数列F[k]=F[k-1]+F[k-2]的性质,可以得到(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1,该式说明:只要顺序表的长度为F[k]-1,则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段,即如上图所示。从而中间位置为mid=low+F(k-1)-1 (2)类似的,每一子段也可以用相同的方式分割 (3)但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只要能使得F[k]-1恰好大于或等于n即可。由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n位置的值即可。 ```java while(n>fib(k)-1) k++; ``` **菲波那切查找应用案例** 请对一个有序数组进行斐波那契查找{1,8,10,89,1000,1234},输入一个数看看该数组是否存在此数,并且求出下标,如果没有就提示“没有这个数”。 ```java public class FibonacciSearch { public static int maxSize=20; public static void main(String[] args) { int[] arr={1,8,10,89,1000,1234}; System.out.println("index="+fibSearch(arr,89)); } //因为后面我们mid=low+F(k-1)-1,需要使用到菲波那切数列,因此我们需要先获取到一个斐波那契数列 //非递归方法得到一个菲波那切数列 public static int[] fib(){ int[] f = new int[maxSize]; f[0]=1; f[1]=1; for (int i=2;i
f[k]-1){ k++; } //因为f[k]值可能大于a 的长度,因此我们需要使用Arrays类,构造一个新的数组,并指向temp[] //不足的部分会使用0填充 int[] temp= Arrays.copyOf(a,f[k]); //实际上需求使用a数组最后的数填充temp //举例: //temp={1,8,10,89,1000,1234,0,0}=>{1,8,10,89,1000,1234,1234,1234} for(int i=hight+1;i
temp[mid]){//我们应该继续向数组的后面查找(右边) low = mid + 1; //为什么是k-=2 //说明 //1.全部元素 = 前面的元素 + 后边元素 //2.f[k]=f[k-1]+f[k-2] //因为后面有f[k-2]个元素,所以可以继续拆分f[k-1]=f[k-3]+f[k-4] //即 在 f[k-2]的前面继续查找k-=2 //即下次循环 mid=f[k-1-2]-1 k-=2; }else {//找到 //需要确定,返回的是哪个下标 if(mid<=hight){ return mid; }else { return hight; } } } return -1; } } ``` > 运行结果 ``` index=3 ``` [1]: https://lilinchao.com/usr/uploads/2020/02/1717463292.png [2]: https://lilinchao.com/usr/uploads/2020/02/2298635431.png
标签:
数据结构和算法
,
查找
非特殊说明,本博所有文章均为博主原创。
如若转载,请注明出处:
https://lilinchao.com/archives/561.html
上一篇
数据结构和算法学习--插值查找算法
下一篇
数据结构和算法学习--哈希表
取消回复
评论啦~
提交评论
栏目分类
随笔
2
Java
326
大数据
229
工具
31
其它
25
GO
40
标签云
线程池
字符串
二叉树
队列
Elastisearch
设计模式
JavaSE
链表
DataWarehouse
序列化和反序列化
人工智能
Tomcat
LeetCode刷题
SQL练习题
RSA加解密
递归
国产数据库改造
Sentinel
并发线程
Scala
Java阻塞队列
数据结构
Nacos
NIO
机器学习
CentOS
正则表达式
Java工具类
Golang基础
前端
友情链接
申请
范明明
庄严博客
Mx
陶小桃Blog
虫洞