java学习笔记(数据结构与算法7)查找专题-斐波那契查找,自身理解+代码实现,斐波那契查找的好处。
2021/9/12 17:06:42
本文主要是介绍java学习笔记(数据结构与算法7)查找专题-斐波那契查找,自身理解+代码实现,斐波那契查找的好处。,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
斐波那契查找的理解:
要理解斐波那契查找,首先要知道它的优点,虽然它和二分查找一样,时间复杂度为O(log2n),但斐波那契查找过程中,只涉及到加减法,不涉及到乘法,因此在查找速度上是有所提升的。
斐波那契查找分为创建新数组和查找两部分。
首先我们先了解一下斐波那契数列,斐波那契数列中的数据满足前两个为1,后面每个值等于前面两个的和,这样我们就仅仅用加法实现了一个接近成倍递增的数列。
创建新数组的作用是使其长度等于斐波那契数列中的数据。从而每次查找都能从中间分为左右两个,同时左右都是斐波那契数列中的数据,可以再分。
查找过程,我们就按照斐波那契数列的数据进行拆分查找,min比key小就查右边,大就查左边。值得一提的是,min=begin+feiBo(k-1)-1;
k-1同学们应该还好理解把,因为现在的头尾一共是feiBo(k),可以分为前面feiBo(k-1)和后面feiBo(k-2)我们用前面begin加上长度feiBo(k-1)即可,而为什么还要-1。对于某些情况,这里-1不-1都行,因为我们只是找一个mid和key比较。但是当begin=end的时候,如果没有-1就会出现错误,因为此时feiBo(k-1)一定为1(这里我不细说了),此时mid如果为begin+feiBo(k-1)就会超过end。
还有一点,因为后面的数据是我们补充的,所以最后找的结果后要判断一下。
下面直接上代码。有不懂的可以和我讨论。
代码里有几个中间过程的输出,可以帮助你理解。
package Search; import java.util.Arrays; public class FeiBoNaQi { public static void main(String[] args) { int[] arr={1,5,12,15,24,27,34,35,45}; System.out.println(search(arr,24)); } public static int search(int[] arr,int key){ int length=arr.length;//由于后面多出要使用arr的长度,所以这里用一个变量表示。 int[] feiBo=new int[length]; feiBo[0]=1; feiBo[1]=1; for(int i=2;i<length;i++){ feiBo[i]=feiBo[i-1]+feiBo[i-2]; } int k=0;//k表示斐波那契数列的下标 while(arr.length>feiBo[k]){ k++; } //创建一个长度略大于arr的长度且为斐波那契数的新数组 int[] temp=Arrays.copyOf(arr,feiBo[k]); for(int l=length;l<feiBo[k];l++){ temp[l]=arr[length-1]; } for(int i=0;i<temp.length;i++){ System.out.print(temp[i]+" "); } System.out.println(); int begin=0; int end=feiBo[k]-1; int mid=0; while(begin<=end){ mid=begin+feiBo[k-1]-1; System.out.println("mid="+mid); if(key<temp[mid]){ end=mid-1; k--; }else if(key>temp[mid]){ begin=mid+1; k-=2; }else{ if(mid<=length-1){ return mid; }else{ return length-1; } } } return -1; } }
这篇关于java学习笔记(数据结构与算法7)查找专题-斐波那契查找,自身理解+代码实现,斐波那契查找的好处。的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)