数据结构与算法——Java实现查找算法—斐波那契查找、插值查找、线性查找

骑猪看日落 2024-03-30 12:14 82阅读 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博客][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 <midVal){
    //           小，向左
                return binarySearch(arr,left,mid-1,findVal);
            }else {
    //          这是最终找到的时候退出递归
                return mid;
            }
    
    
        }
    
    }

### 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<Integer> binarySearch(int[] arr, int left, int right, int findVal){
    
    
    //      这种是没有找到的时候退出递归退出递归
            if(left>right){
                return new ArrayList<Integer>();
            }
    
            int mid=(left+right)/2;
            int midVal = arr[mid];
    
            if(findVal >midVal){
    //            大，找右边的
               return binarySearch(arr,mid+1,right,findVal);
            }else if(findVal <midVal){
    //           小，向左
                return binarySearch(arr,left,mid-1,findVal);
            }else {
    //          这是最终找到的时候退出递归
                ArrayList<Integer> 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，其余移动到右侧，便是下面的公式**

![49b3202c6f3a42aaa04293fb95aed56a.png][]

![e2af7fb812b14e42978e31714a3da418.png][]

### 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;
            }
    
    //       求出mid
            int 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<midVal){
                return insertValueSearch(arr,left,mid-1,findVal);
            }else
    
    //     如果上面的两个if没有运行，则指定运行下面这个return
            return mid;
        }
    }

## 四、斐波那契（黄金分割法）查找算法 ##

参考下面两份资料

[https://www.cnblogs.com/sha-Pao-Zi/p/16315064.html![icon-default.png_t_N176][]https://www.cnblogs.com/sha-Pao-Zi/p/16315064.html][https_www.cnblogs.com_sha-Pao-Zi_p_16315064.html_icon-default.png_t_N176_https_www.cnblogs.com_sha-Pao-Zi_p_16315064.html]

[36-查询算法-斐波那契查找3-分解1数组准备\_哔哩哔哩\_bilibili![icon-default.png_t_N176][]https://www.bilibili.com/video/BV1ga411b7qF?p=37&spm\_id\_from=pageDriver&vd\_source=c01240addcba226237f3c4781490fbae][36-_-_3-_1_bilibili_icon-default.png_t_N176_https_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**

![20210505200936345.png][]

*   类似的，每一子段也可以用相同的方式分割
 *  但顺序表长度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 难点解析图 ###

![b965e5226c08470d8e2d9b29cb2114dc.png][]

其实对于**(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都没有返回表示没有找到对应的内容，则返回-1
            return -1;
        }
    
    }

[JavaSE_-CSDN]: https://blog.csdn.net/weixin_51351637/article/details/127856083
[49b3202c6f3a42aaa04293fb95aed56a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a4f48203655d46678f32fa57c8765583.png
[e2af7fb812b14e42978e31714a3da418.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5ab78113d8a448db8986fdeb56fd9584.png
[icon-default.png_t_N176]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/92fc523042a24609bc5b56b0e10aca5e.png
[https_www.cnblogs.com_sha-Pao-Zi_p_16315064.html_icon-default.png_t_N176_https_www.cnblogs.com_sha-Pao-Zi_p_16315064.html]: https://www.cnblogs.com/sha-Pao-Zi/p/16315064.html
[36-_-_3-_1_bilibili_icon-default.png_t_N176_https_www.bilibili.com_video_BV1ga411b7qF_p_37_spm_id_from_pageDriver_vd_source_c01240addcba226237f3c4781490fbae]: https://www.bilibili.com/video/BV1ga411b7qF?p=37&spm_id_from=pageDriver&vd_source=c01240addcba226237f3c4781490fbae
[20210505200936345.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a175fd404478401ea190ef8ac32fef32.png
[b965e5226c08470d8e2d9b29cb2114dc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fcfd71fc66fb4c689d4b9cd4944e711b.png