数据结构与算法——Java实现查找算法—斐波那契查找、插值查找、线性查找
创始人
2024-05-31 20:02:42
0

目录

一、线性查找

1.1 代码实现

二、二分查找

2.1 思路分析

2.2  代码实现(递归)

 2.3  改善二分查找法——返回所有相同的数字下标

三、插值查找

3.1 思路分析

3.2 代码实现

四、斐波那契(黄金分割法)查找算法

4.1 原理

4.2  难点解析图

4.3 代码


常用查找:

  • 顺序(线性)查找
  • 二分查找(折半查找)
  • 插值查找
  • 斐波那契查找

一、线性查找

最简单的一个查找,没有比这个算法再简单的了

思路:逐一比对,发现有相同值时便返回

1.1 代码实现

   问题:找到我们要寻找的数的下标并返回,如果找不到返回-1

   如果是返回多个的话,我们可以把值存放到一个数组当中

public class SeqSearch {public static void main(String[] args) {int arr[] ={1,9,11,-1,34,89};int index = seqSearch(arr, -1);System.out.println(index);}public static int seqSearch(int[] arr,int value){for(int i=0;i< arr.length;i++){if(arr[i] == value){return i;}}
//    没找到return -1;}
}

二、二分查找

前提:在有序数组中

2.1 思路分析

下面的思路分析是基于数组是从小到大有序排序的时候(如果是从大到小,下面的第二步应该反过来 )

  •  首先确定该数组的中间的下标

              mid = (left + right) / 2

  •   然后让需要查找的数 findVal 和 arr[mid] 比较

              findVal > arr[mid] ,  说明你要查找的数在mid 的右边, 因此需要递归的向右查找
              findVal < arr[mid], 说明你要查找的数在mid 的左边, 因此需要递归的向左查找
              findVal == arr[mid] 说明找到,就返回

  •  什么时候我们需要结束递归

              找到就结束递归

              递归完整个数组,仍然没有找到findVal ,也需要结束递归  当 left > right 就需要退出

2.2  代码实现(递归)

下面这种是普通方法实现

JavaSE——选择排序算法、冒泡排序法、二分查找法_我爱布朗熊的博客-CSDN博客

下面这种是使用递归实现

// 二分查找必须是有序的
public class BinarySearch {public static void main(String[] args) {int arr[] = {1,8,10,89,100,1234};System.out.println(binarySearch(arr,0,arr.length-1,1234));}
//  返回-1表示没有找到,找到了就返回下标public static int binarySearch(int[] arr,int left,int right,int findVal){//      这种是没有找到的时候退出递归退出递归if(left>right){return -1;}int mid=(left+right)/2;int midVal = arr[mid];if(findVal >midVal){
//            大,找右边的return binarySearch(arr,mid+1,right,findVal);}else if(findVal 

 2.3  改善二分查找法——返回所有相同的数字下标

// 二分查找必须是有序的
public class BinarySearch {public static void main(String[] args) {int arr[] = {1,8,10,89,100,100,100,100,1234};System.out.println(binarySearch(arr,0,arr.length-1,100));}
//  返回-1表示没有找到,找到了就返回下标public static ArrayList binarySearch(int[] arr, int left, int right, int findVal){//      这种是没有找到的时候退出递归退出递归if(left>right){return new ArrayList();}int mid=(left+right)/2;int midVal = arr[mid];if(findVal >midVal){
//            大,找右边的return binarySearch(arr,mid+1,right,findVal);}else if(findVal  resIndexList = new ArrayList<>();int temp =mid-1;//          因为我们这是二分查找法,所以我们最终找到的数的两边都有可能和这个数相等while (true){if(temp<0 || arr[temp] != findVal){break;}resIndexList.add(temp);temp--;}resIndexList.add(mid);//          再从中间向右temp = mid+1;while (true){if(temp> arr.length-1  || arr[temp] != findVal){break;}resIndexList.add(temp);temp++;}return  resIndexList;}}
}

三、插值查找

    插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找

    对于数据量大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快

     关键字分布不均匀的情况下,该方法不一定比折半查找要好 

3.1 思路分析

下面的公式一眼看上去很复杂,但是稍微一转变,很好记

(mid-left)/(right-left) = (findVal - arr[left])/(arr[right]-arr[left])

左边是下标,右边对应值

上面的公式,将左侧剩余mid,其余移动到右侧,便是下面的公式

3.2 代码实现

public class InsertValueSearch {public static void main(String[] args) {int[] arr = new int[100];//      初始化数组for (int i = 0; i < 100; i++) {arr[i] = i + 1;}int search = insertValueSearch(arr, 0, arr.length - 1, 101);System.out.println(search);}/*** 前提:这个数组是有序的** @param arr     传入的数组* @param left    左边的索引* @param right   右侧的索引* @param findVal 要查找的值* @return 最终查到的这个值的索引,如果没有找到就返回-1*/public static int insertValueSearch(int[] arr, int left, int right, int findVal) {//      退出的条件:
//        左侧的下标大于右侧的下标,不现实,肯定退出if (left > right || findVal < arr[left] || findVal > arr[right]) {return -1;}//       求出midint mid =left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);int midVal = arr[mid];if(findVal>midVal){
//           说明向右侧递归查找return insertValueSearch(arr,mid+1,right,findVal);}else if(findVal

四、斐波那契(黄金分割法)查找算法

参考下面两份资料

https://www.cnblogs.com/sha-Pao-Zi/p/16315064.htmlhttps://www.cnblogs.com/sha-Pao-Zi/p/16315064.html

36-查询算法-斐波那契查找3-分解1数组准备_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1ga411b7qF?p=37&spm_id_from=pageDriver&vd_source=c01240addcba226237f3c4781490fbae

      黄金分割点是指把一条线段分割成两部分,使其中一部分与全长之比等于另一部分与这一部分之比。取其前三位数字的近似值是0.618.由于按此比例设计的造型十分美丽,因此称为黄金分割,也称中外比。

     斐波那契数列{1,1,2,3,5,8,13,21,34,55}发现斐波那契数列的两个相邻数的比例,无限接近黄金分割值0.618,即将mid值设置成神器的黄金分割点(0.618)的位置

    这个数列的后一个数是前两个数之和,如8=5+3

4.1 原理

      与二分查找法、插值查找法相似,仅仅改变了中间节点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近

       即mid=low+F(k-1)-1,其中F代表斐波那契数列,low是数组最左侧元素的索引,k代表斐波那契数列的第几个元素

   

对F(k-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

  •     类似的,每一子段也可以用相同的方式分割
  •     但顺序表长度n不一定刚好等于F[k]-1,所以需要将原来的顺序表长度n增加至F[k]-1。这里的k值只能使得F[k]-1恰好大于或等于n即可,由以下代码得到,顺序表长度增加后,新增的位置(从n+1到F[k]-1位置),都赋为n位置的值即可。
while(n>fib(k)-1)k++;

注意, 此时斐波那契数列是存放在数组中的, 所以会用F[]表示, 一定要注意跟F()的不同, 比如: F[6] =13 = F(7), F[0] = 1 = F(1)

4.2  难点解析图

其实对于(F[k]-1)=(F[k-1]-1)+(F[k-2]-1)+1 及 mid=low+f(k-1)-1  还有另外一种理解方式,我不知道对不对,但是我感觉很有道理

    最开始的 数组的长度是f(k) = f(k-1)+f(k-2),此时代表的是长度,一定要注意

   但是当我们获取下数组的时候就需要长度-1,数组的原因 变成了  (F[k]-1)

   然后我们把数组分成了三部分,左侧的部分的数组下标到f[k-1]-1,右侧到f[k-2]-1,但是此时我们中间还有一个mid,所示再+1(占一个下标的位子),故(F[k-1]-1)+(F[k-2]-1)+1

  我觉得还是用上面的图理解更为合适,上面的图是从很多地方整理结合出来的,下面的文字是我自己想的有点不太对

4.3 代码

public class FibSearch {private static int maxSize = 20;public static void main(String[] args) {int[] arr = {1,8,10,89,1000,1234};System.out.println(fibSearch(arr,1234));}public static int[] fib() {int[] f = new int[maxSize];f[0] = 1;f[1] = 1;for (int i = 2; i < maxSize; i++) {f[i] = f[i - 1] + f[i - 2];}return f;}/*** @param a   数组* @param key 我们需要查找的关键码值* @return 返回对应的下标,如果没有-1*/public static int fibSearch(int[] a, int key) {int low = 0;int high = a.length - 1;  //high下标对应的数据就是数组中最大的数int k = 0;  //表示斐波那契分割数值的下标int mid = 0;  //存放mid值int f[] = fib(); //获取斐波那契数列//       获取到斐波那契分割数值的下标
//       为什么不写a.length()>f[k]? 而是两边同时-1成为high >f[k]-1 ?
//           应该也是可以的  这个的目的就是找出一个f[k]>=a.length的while (high > f[k] - 1) {
//           进入循环相当于没找到k++;
//            退出的条件  a.length()<=f[k]}//      f[k]的值可能大于数组a的长度,因此我们需要使用Arrays类构造一个新的数组(临时数组)并指向a[]
//        if (f[k] > a.length) {  } 此时这里不用if语句判断f[k] > a.length,因为因为上面while的缘故f[k]>=a.length是一定的
//      将a数组拷贝到temp数组,并且temp数组的长度是f[k]的值,int[] temp = Arrays.copyOf(a, f[k]);
//       新扩充的地方用0补齐,但是我们需要用a数组的最后一位补齐,我们还得改一下temp数组for (int i = a.length; i < temp.length; i++) {temp[i] = a[a.length - 1];}while (low <= high) {
//           只要这个条件满足就一直找mid = low + f[k - 1] - 1;  //黄金分割点if (key < temp[mid]) {
//              向左找high = mid - 1;
//              为什么是k--?
//                  全部元素=f[k-1]+f[k-2]
//                  f[k] = f[k-1] + f[k-2]
//                  因为前面有f[k-1]个元素,这个f[k-1]依然可以再拆分
//                  带入公式变为f[k-1]=f[k-1-1]+f[k-1-2] 在前面的一部分找一个黄金分割点 高一知识k--;} else if (key > temp[mid]) {
//               向右low = mid + 1;
//              为什么是k=k-2?
//                全部元素=f[k-1]+f[k-2]
//                我们后面有k-2个元素,再对k-2进行拆分,把k-2个元素的部分想象成整个部分来看
//                f[k-2]=f[k-2-1]+f[k-2-2]  在后一部分找一个黄金分割点、满足斐波那契查找
//                最终就是下面的公式k = k - 2;} else {
//              找到了,但是需要判断返回的下标if (mid <= a.length-1) {
//                表示这个就是在原始的数组内找到的,并不是在扩容之后的内容return mid;}else {
//                在扩容的内容里找到的return a.length-1;}}}
//      整个while都没有返回表示没有找到对应的内容,则返回-1return -1;}}

相关内容

热门资讯

安卓双系统添加应用,轻松实现多... 你有没有想过,你的安卓手机里可以同时运行两个系统呢?听起来是不是很酷?想象一边是熟悉的安卓系统,一边...
pipo安卓进系统慢,探究pi... 最近是不是发现你的Pipo安卓系统更新或者运行起来特别慢?别急,今天就来给你好好分析分析这个问题,让...
怎样使用安卓手机系统,安卓手机... 你有没有发现,安卓手机已经成为我们生活中不可或缺的一部分呢?从早晨闹钟响起,到晚上睡前刷剧,安卓手机...
双系统安卓安装caj,轻松实现... 你有没有想过,你的安卓手机里装上双系统,是不是就能同时享受安卓和Windows系统的乐趣呢?没错,这...
安卓使用ios系统教程,安卓用... 你是不是也和我一样,对安卓手机上的iOS系统充满了好奇?想要体验一下苹果的优雅和流畅?别急,今天我就...
安卓系统gps快速定位,畅享便... 你有没有遇到过这样的情况:手机里装了各种地图导航软件,但每次出门前都要等上好几分钟才能定位成功,急得...
安卓手机系统更新原理,原理与流... 你有没有发现,你的安卓手机最近是不是总在提醒你更新系统呢?别急,别急,让我来给你揭秘一下安卓手机系统...
安卓系统通知管理,全面解析与优... 你有没有发现,手机里的通知就像是一群调皮的小精灵,时不时地跳出来和你互动?没错,说的就是安卓系统的通...
安卓系统手机哪买,揭秘哪里购买... 你有没有想过,拥有一部安卓系统手机是多么酷的事情呢?想象你可以自由安装各种应用,不受限制地探索各种功...
安卓系统 ipv4,基于安卓系... 你知道吗?在智能手机的世界里,有一个系统可是无人不知、无人不晓,那就是安卓系统。而在这个庞大的安卓家...
目前安卓是什么系统,探索安卓系... 亲爱的读者,你是否曾好奇过,如今安卓系统究竟是什么模样?在这个科技飞速发展的时代,操作系统如同人体的...
安卓6.0系统比5.0,从5.... 你有没有发现,自从手机更新了安卓6.0系统,感觉整个人都清爽了不少呢?没错,今天咱们就来聊聊这个话题...
安卓2.36系统升级,功能革新... 你知道吗?最近安卓系统又来了一次大变身,那就是安卓2.36系统升级!这可不是一个小打小闹的更新,而是...
安卓系统源码怎么打开,并可能需... 你有没有想过,安卓系统的源码就像是一扇神秘的门,隐藏着无数的技术秘密?想要打开这扇门,你得掌握一些小...
安卓8.0系统体验视频,智能革... 你有没有听说安卓8.0系统最近可是火得一塌糊涂啊!作为一个紧跟科技潮流的数码达人,我当然要来给你好好...
宣传系统漫画app安卓,探索安... 亲爱的读者们,你是否曾在某个午后,百无聊赖地打开手机,想要寻找一些轻松愉悦的读物?今天,我要给你介绍...
鸿蒙替换安卓系统吗,开启智能生... 你知道吗?最近科技圈里可是炸开了锅,因为华为的新操作系统鸿蒙系统,据说要大举进军手机市场,替换掉安卓...
手机安卓系统深度清理,解锁手机... 手机里的东西是不是越来越多,感觉就像一个装满了杂物的储物柜?别急,今天就来教你一招——手机安卓系统深...
安卓上的windows系统,融... 你有没有想过,在安卓手机上也能体验到Windows系统的魅力呢?没错,这就是今天我要跟你分享的神奇故...
安卓系统焦点变化事件,Andr... 你知道吗?在安卓系统的世界里,最近发生了一件超级有趣的事情——焦点变化事件。这可不是什么小打小闹,它...