🐻前言:

        哎呀,学的太快,博主糊涂了,整理了一下发现查找算法居然没将,大意了,今天呢,咱们先放放堆排序,先看看咱们这个查找算法,查找算法呢有三种,有我们喜闻乐见的二分查找算法,哎呀,大家都学透了,但是呢,今天我重点介绍的是插值和斐波那契,给大家耳目一新.

        我会从以下几点开始阐述:

        查找算法的基础知识铺垫 🔜 查找算法的概述 🔜 查找算法的创建思路 🔜 查找算法的代码实现与分析 🔜 查找算法的总结

        如果喜欢博主的话,戳这    传送门

        精彩频道:

                SQL的DBMS区 🔛 Java的数据结构区 🔛 SE的基础知识点区

        往期精彩:

               强哥带你去搬树

目录

🐻前言:

🦁查找算法的的基础知识铺垫:

😙斐波那契数列的定义:

🦁查找算法的概述: 

🐼暴力查找:

🐼二分查找:

🐼插值查找: 

🐼斐波那契查找: 

🦁查找算法的创建思路

🐼二分查找算法(递归的方式): 

🐼插值查找算法(递归的方式): 

🐼斐波那契查找算法(循环的方式):

😶‍🌫️注意: 

😀1.二分查找算法的代码实现与分析(普通版): 

🥸代码分析: 

😀2.二分查找法的代码实现和分析(升级版) 

🥸代码分析:

😀3.插值查找算法(普通法):

🥸代码分析:

😀4.插值查找算法(升级版): 

🥸代码分析:

😀5.斐波那契查找算法(普通版): 

5.1建立一个斐波那契数列的方法🎆

🥸代码分析:

5.2创建斐波那契查找的方法 🎆

🥸代码分析:

🐻结论: 

🦁查找算法的的基础知识铺垫:

😙斐波那契数列的定义:

        如果在一个数列中,除了第一个元素和第二个元素是1,其他元素是前两个元素之和,我们称这样的数列为斐波那契数列

        样例:[1,1,2,3,5,8,13.....]

🦁查找算法的概述: 

🐼暴力查找:

        暴力查找顾名思义,就是不用动脑子一个一个去遍历比较,用最朴素的代码完成最朴素的任务,因为这个算法太过简单了,这个代码就不写了也不分析了,相信大家都会的.

🐼二分查找:

        二分查找是最熟悉的了,二分查找又被称为折半查找,通过左索引右索引与中间索引的动态变化从而大大提高查找的效率,接下来会是重点阐述对象之一,因为接下来的两种算法是以二分查找的思路为基础的.

🐼插值查找: 

        插值查找是对于初学者来说较为陌生的一个算法,不过,该算法写起来与二分查找算法极度相似,只是有个别小点不相同,注意的是,由于该算法太NB了,我也搞不懂里面的思想,只能教大家怎么去写,不过也不难写,放心哦

🐼斐波那契查找: 

        斐波那契查找算法顾名思义,里面用到了斐波那契数列,斐波那契查找算法也被称为黄金分割查找算法,故要找到黄金分割点去查找我们需要的元素,相对而言,斐波那契查找算法是查找算法里面最优的算法,故,我会着重讲述斐波那契查找算法的 

🦁查找算法的创建思路

🐼二分查找算法(递归的方式): 

1. 创建一个查找算法,参数列表有left,right,findValue,array
2. 创建一个变量mid,通过left和right获取mid
3. 通过对mid的比较,决定递归方向
4. 最后判断是否能找到

🐼插值查找算法(递归的方式): 

1. 创建一个查找算法,参数列表有left,right,findValue,array
2. 创建一个变量mid,通过left和right获取mid
3. 通过对mid的比较,决定递归方向
4. 最后判断是否能找到

🐼斐波那契查找算法(循环的方式):

1. 创建一个方法,用于构建斐波那契数列,并返回斐波那契数列
2. 将带查找的数组长度与斐波那契数列里面的值去比较,找一个合适的值
3. 若数组的个数不够,则在后面补最后一个结果,补刀数值相同为止
4. 创建一个变量mid,通过left和right获取mid
5. 通过特殊的转换关系继续循环(等等会具体阐述)

😶‍🌫️注意: 

        以上的算法都是建立在有序的基础上的,如果带查找序列是无序序列,不能用以上三种算法,只能暴力查找算法,谨记! 

        一下算法遵循此原则:如果找到了该元素,如果就会将该元素的下标返回回来,否则返回-1

                                         如果找到了多个元素,就将该集合放回回来

😀1.二分查找算法的代码实现与分析(普通版): 

public static int binarySearchSingle(int[] array,int left,int right,int findValue) { if(left > right || findValue > array[length-1]) {     return -1; } var mid = left + 1/2*(right - left); var midValue = array[mid]; if(findValue > midValue) {     return binarySearchSingle(array,mid+1,right,findValue); }else if(findValue < midValue) {     return binarySearchSingle(array,left,mid-1,findValue); }else {     return mid; }    }

🥸代码分析: 

1. left是左索引,right是右索引,应该一开始就被赋值为0与array.length-1(因为带查找的值在他们两个索引之间,即[left,right]区间内有带查找元素)
2. findValue是待查找的值,array是带查找的数组
3. 二分查找法顾名思义是折半,所以mid = 1/2(left + right) = left + 1/2*(right - left)
4. 注意:后面的表达式非常的重要,是折半查找发的关键
5. 将mid下标对应的值放入midValue
6. 情况:
   1. 如果midValue大于findValue,由于有序,说明待查找的元素在mid右边且不为mid,所以得出了[mid+1,right]的范围内有带查找元素,故left =  mid+1
   2. 如果midVvalue小于findValue,由于有序,说明带查找的元素在mid左边且不为mid,所以得出了[left,mid-1]的范围内有带查找元素,故right = mid-1
   3. 如果midValue = findValue,说明找到了该元素,直接返回mid即可,mid是下标
   4. 如果left > right,由于没有这样的区间(即区间左边必须小于右边的值),说明找不到,直接返回-1
7. 如果findValue大于列表的最后一个值,由于有序,最后一个值为最大值,说明列表里面不可能有与findValue相同的值,直接返回-1

😀2.二分查找法的代码实现和分析(升级版) 

 public static List binarySearchMore(int[] array,int left,int right,int findValue) { if(left > right || findValue > array[length-1]) {     return new ArrayList(); } var mid = (left + right)/2; var midValue = array[mid]; if(findValue > midValue) {     return binarySearchMore(array,mid+1,right,findValue); }else if(findValue < midValue) {     return binarySearchMore(array,left,mid-1,findValue); }else {     var list = new ArrayList();     list.add(mid);     var temp = mid - 1;     while(temp > 0 && array[temp] == findValue) {  list.add(temp--);     }     temp = mid + 1;     while (temp < array.length && array[temp] == findValue) {  list.add(temp++);     }     return list; }

🥸代码分析:

1. 注意:由于其他代码都一样,我们重点分析一下else里面的代码
2. 当程序进入else时,说明找到了该元素,由于我们要实现多元素返回,我们可以借助集合,故我们要new一个ArrayLsit
3. 先将该元素add进去集合中
4. 创建一个辅助索引temp,赋值为mid-1(目的:向左遍历)
5. 通过while循环,如果temp>0(防止数组下标越界异常),且array[temp] = findValue,说明此元素也是我们要找的元素,添加入集合中
6. 如果while布尔表达式为false,说明temp遍历到了最左边或是不相等,由于列表的有序性,如果不相等,则前面的元素一定比midValue小,不可能再有带查找的元素,直接结束向左遍历
7. temp赋值为mid+1(目的:向右遍历)
8. 同理5~6
9. 最后返回list即可
10. 特别注意的是,如果找不到,我们返回一个空的集合,所以在最前面new了一个空集合

😀3.插值查找算法(普通法):

public static int interpolateSearch(int[] array,int left,int right,int findValue) { if(left > right || findValue  array[array.length-1]) {     return -1; } var mid = left + (right - left)*(findValue - array[left])/(array[right] - array[left]); var midValue = array[mid]; if(findValue > midValue) {     return interpolateSearch(array,mid+1,right,findValue); }else if(findValue < midValue) {     return interpolateSearch(array,left,mid-1,findValue); }else {     return mid; }    }

🥸代码分析:

1. 插值查找算法唯一的不同就是mid的变化
2. mid =  left + (right-left)((findValue - array[left])/(array[right]-array[left]))
3. 其他都一致,只需知道mid的赋值即可

😀4.插值查找算法(升级版): 

public static List interpolateSearchMore(int[] array,int left,int right,int findValue) { if(left > right || findValue > array[array.length-1] || findValue < array[0]) {     return new ArrayList(); } var mid = left + (findValue - array[left])/(array[right] - array[left]) * (right - left); var midValue = array[mid]; if(findValue > midValue ) {     return interpolateSearchMore(array,mid+1,right,findValue); }else if(findValue < midValue ) {     return interpolateSearchMore(array,left,mid-1,findValue); }else {     var list = new ArrayList();     list.add(mid);     // 短路与有学问呢     for (int temp = mid + 1;temp  0 && array[temp] == findValue ; temp++)  list.add(temp);     return list; }    }

🥸代码分析:

        略~~ 

😀5.斐波那契查找算法(普通版): 

5.1建立一个斐波那契数列的方法🎆

   public static int[] fibonacci() { var array = new int[20]; array[0] = 1; array[1] = 1; for (int i = 2; i < array.length; i++) {     array[i] = array[i-1] + array[i-2]; } return array;    }

🥸代码分析:

1. 创建一个数组,用于存放斐波那契数列(长度可以随意)
2. 将第一个和第二个元素赋值为1
3. 建立循环,从第三个元素开始(即下标为2),当前元素的值是前两个元素之和
4. 返回该数组 

5.2创建斐波那契查找的方法 🎆

public static int fibonacciSearch(int[] array,int key) { var low = 0; var high = array.length-1; var mid = 0; var midValue = 0; var k = 0; var f = fibonacci(); while(high > f[k] - 1){     k++; } var temp = Arrays.copyOf(array,f[k]); for (int i = high+1; i < temp.length ; i++) {     temp[i] = array[high]; } while(low  midValue) {  low = mid+1;  k-=2;     }else if(key < midValue) {  high = mid-1;  k-=1;     }else {  return Math.min(mid, high);     } } return -1;    }

🥸代码分析:

1. low(左索引),right(右索引),mid(索引),midValue(索引对应的值),k(用于遍历斐波那契数组的索引),f(用于接收斐波那契数组)
2. 注意:
   1. 斐波那契数组里面的值表示带查找数组的元素个数
3. 第一步:我们要将斐波那契数组的索引k移动,移动至与数组元素相近的为止
   1. 有可能斐波那契数组里面的元素的值比数组的总长度大
   2. 有可能斐波那契数组里面的元素的值等于数组的总长度
   3. 注意:由于high是下标.比总长度少了1,所以在比较的时候在斐波那契数组k下标对应值上-1
4. 第二步:我们要进行数组扩容的操作,拷贝后的长度是斐波那契数组中索引k对应的值
   1. 目的:因为数组长度严格符合斐波那契数组里面的元素值,才能找得到该数组的黄金分割点
   2. 无论是否是哪种情况,该做法是最安全的
5. 第三步:利用循环在扩容的部分赋值原数组的最后一个元素,即temp[i] = array[high];
6. 第四步:利用while循环去找所需求的值
   1. low<=high与上述一致,在这个区间内有我们要找的元素
   2. mid 赋值为f(k-1) -1
      1. 如果有f(k)个元素,那么黄金分割点前有f(k-1)个元素,黄金分割点后有f(k-2)个元素
      2. 因为有下标的因素,所以这里要-1
   3. 将黄金分割点对应下标的值赋予midValue
   4. 如果midValue < key,说明待寻找的值在黄金分割点的右边
      1. 故low = mid+1,表示在此区间有我们想要的元素
      2. 注意的是:此刻元素总数会从f(k)变成f(k-2),所以此刻要k-=2,让元素个数再次与斐波那契数组k对应元素一致,再次形成黄金分割点
   5. 如果midValue > key,说明带寻找的值在黄金分割点的左边
      1. 故high = mid -1,表示在此区间有我们想要的元素
      2. 注意的是:此刻元素总数从f(k)变成f(k-1),所以此刻要k-=1
   6. 如果midValue = key说明找到了
      1. 注意的是,有可能找到的元素下标比原数组最大下标大
      2. 故当我们发现找到的值比原数组最大下标大时,我们需要返回原数组最大下标
         1. 因为后面的元素都是用最后一个元素去补充的
   7. 循环结束后都找不到,说明真找不到了,直接返回-1

🐻结论: 

        查找算法说难不难,说易不易,主要是对二分查找法认识,自然而然的就会写插值查找发,不过最重要的还是斐波那契查找算法,他有效利用了斐波那契数组所体现出来的黄金分割思想,最后,我来总结一下几点:

        1.二分查找法怎么去找,怎么去想

        2.斐波那契查找怎么利用斐波那契数组,以及k的变化

        🚇下一站:堆排序

伪原创接口