二分查找、折半查找（Java）

骑猪看日落 2024-04-07 10:27 83阅读 0赞

#### 目录 ####

*   *   *  7.3 二分（折半）查找
         *   *  二分查找（递归）
             *  二分查找（非递归）
         *  7.4 插值查找算法
         *  本次二分、插入查找教程出自韩顺平的数据结构与算法

#### 7.3 二分（折半）查找 ####

##### 二分查找（递归） #####

注意事项：二分查找适合的对象是**有序序列**

*  思路分析

1、首先确定该数组的中间下标mid = （left+right） / 2

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

*  findVal>arr\[mid\]，说明需要查找的数在mid的右边，递归向右查找
 *  findVal<arr\[mid\]，说明需要查找的数在mid的左边，递归向左查找
 *  findVal == arr\[mid\]，说明找到，返回该值或下标

//什么时候结束递归

1）找到就结束递归

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

**代码实现**

![在这里插入图片描述][11e2e692979e4e05b714cbb8d2a8d0fb.png]

package com.ldm.search;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * @author 梁东明
     * 2022/8/30
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     * 二分查找（折半）查找（适用于有序序列）
     */
    public class BinarySearch {
        
        public static void main(String[] args) {
        
            int arr[] = {
        1,3,3,3,5,7,9,13,34,45,78};
            /*//切记arr是有序数组！！！！二分查找只适合有序数组
            //我一开始跟着老师代码完全一样就是报 栈溢出 的错误
            //通过debug才发现我的arr一开始是无序的。又一次加深印象了.原来二分查找只适合有序序列。
            int binarySearch = binarySearch(arr, 0, arr.length - 1, 79);
            System.out.println("binarySearch = " + binarySearch);*/
    
            List<Integer> integers = binarySearch2(arr, 0, arr.length - 1, 3);
            System.out.println("值为3的下标分别为 = " + integers);
        }
    
    
        /**
         * //二分查找算法
         * @param arr 被查找的数组
         * @param left 左边的索引
         * @param right 右边的索引
         * @param findVal  要查找的值
         * @return   返回要查找的值或者-1
         */
        public static int binarySearch(int[] arr, int left, int right,int findVal){
        
            int mid = (left + right) / 2;
            int midVal = arr[mid];
            if (left > right){
        
                return -1;
            }
    
            if ( findVal > midVal ){
        
                //开始向右递归
                return binarySearch(arr, mid+1,right,findVal);
            }else if (findVal < midVal){
        
                //开始向左递归
                return binarySearch(arr,left,mid-1,findVal);
            }else {
        
                return mid;
            }
        }
        /**
         * //对二分查找算法优化
         * 即查找的值有多个相同的值，将所有相同的值查找出来
         *
         * 思路分析：
         * 1、找到mid值时不用立即返回。
         * 2、向mid索引值的左边扫描将满足的的相同值的下标保存在集合ArrayList
         * 3、向mid索引值的右边扫描将满足的的相同值的下标保存在集合ArrayList
         * 4、返回ArrayList
         * @param arr 被查找的数组
         * @param left 左边的索引
         * @param right 右边的索引
         * @param findVal  要查找的值
         * @return   返回要查找的值或者-1
         */
        public static List<Integer> binarySearch2(int[] arr, int left, int right, int findVal){
        
            System.out.println("查找次数");
            int mid = (left + right) / 2;
            int midVal = arr[mid];
    
            //这时候不能返回-1啦，要返回一个空的Integer集合
            if (left > right){
        
                return new ArrayList<Integer>();
            }
    
            if ( findVal > midVal ){
        
                //开始向右递归
                return binarySearch2(arr, mid+1,right,findVal);
            }else if (findVal < midVal){
        
                //开始向左递归
                return binarySearch2(arr,left,mid-1,findVal);
            }else {
        
                List<Integer> resIndexList = new ArrayList<>();
               // 2、向mid索引值的左边扫描将满足的的相同值的下标保存在集合ArrayList
                int temp = mid -1;
                while (true) {
        
                    if (temp < 0 || arr[temp] != findVal){
        
                        break;
                    }
                    //将相同的值保存在集合中
                    resIndexList.add(temp);
                    temp --;  //temp左移
                }
                resIndexList.add(mid);
                // 3、向mid索引值的右边扫描将满足的的相同值的下标保存在集合ArrayList
                temp = mid +1;
                while (true) {
        
                    if (temp > arr.length -1 || arr[temp] != findVal){
        
                        break;
                    }
                    //将相同的值保存在集合中
                    resIndexList.add(temp);
                    temp ++;  //temp右移
                }
                return resIndexList;
            }
        }
    }

##### 二分查找（非递归） #####

**前面我们使用过二分查找算法，这我们使用非递归的方法**

1）二分查找只适用于从有序的数列中进行查找（比如数字和字母等），将数列排序后再进行查找

2）二分查找的运行时间为对数时间o(log2n),即查找到需要的目标位置最多只需要log2n步，假设从\[0,99\]的队列（100个数，即n=100）中寻找目标数30，则需要查找步数为log2 100），即最多需要查找7次

**代码实现**

package com.ldm.binarySearchNoRecursion;
    
    /**
     * @author 梁东明
     * 2022/9/10
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     * 二分查找非递归算法
     */
    public class BinarySearchNoRecur {
        
        public static void main(String[] args) {
        
            int[] arr = {
         1,3,5,7,9,12,15,18,21,24,27};
            int i = binarySearch(arr, 24);
            if ( i == -1){
        
                System.out.println("数组中没有该元素");
            }else {
        
                System.out.println("1在数组中的索引是 = " + i);
            }
        }
    
        /**
         * 二分查找非递归
         *
         * @param arr    传进来的有序数组
         * @param target 目标元素
         * @return int   返回该目标元素的下标，没有就返回-1
         */
        public static int binarySearch(int[] arr, int target){
        
            int left = 0;
            int right = arr.length - 1;
            while (left <= right){
          //开始查找
                int mid = (left + right) / 2;
                if (arr[mid] == target){
        //找到就直接返回下标
                    return mid;
                }else if (arr[mid] > target){
        //说明目标元素在数组的左边，在左边继续查找
                    right = mid - 1 ;
                }
                else if (arr[mid] < target){
        //说明目标元素在数组的右边，在右边继续查找
                    left = mid + 1;
                }
            }
            //说明数组中没有该目标，直接返回-1
            return -1;
        }
    }

#### 7.4 插值查找算法 ####

**插值查找算法原理介绍**

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

2）将折半查找中求mid索引的公式，low表示左边索引，high表示右边索引。

![在这里插入图片描述][d4cba95a743049a3b1e07c4465771add.png]

**分享一条助理解的例子给大家看看**

你可以把上面两条公式的 （ 1/2） 与 （key - a\[low\] / a\[high\] -a\[low\] ） 分别取出比较

首先，数组必须是有序序列，

例如： \{1，2，3，4，5\}中找到2，

用（插入查找公式）（key - a\[low\] / a\[high\] -a\[low\] )<==>( 2-1）/（5-1）=1/4

用（二分查找公式）1/2 相比之下1/4比1/2小 ,缩小搜索范围。

**这个式子的意义：所查找的数字的位置占数组总长度的比例**

3）int midIndex = low +（high - low ）\*（key -arr\[low\]) / (arr\[high\] - arr\[low\]); /*插值索引*/

**代码实现**

package com.ldm.search;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    /**
     * @author 梁东明
     * 2022/8/30
     * 人生建议：看不懂的方法或者类记得CTRL + 点击 看看源码或者注解
     * 点击setting在Editor 的File and Code Templates 修改
     * 插值查找
     * 插值查找与二分查找的区别：查找次数比二分查找少；查找的mid值不同
     */
    public class InsertValueSearch {
        
        public static void main(String[] args) {
        
            //先创建一个容量为100，1为第一个值的递增数组
            int arr[] = new int[100];
            for (int i = 0; i < 100; i++) {
        
                arr[i] = i+1;
            }
            int i = insertValueSearch(arr, 0, arr.length - 1, 64);
            System.out.println("64的索引是 = " + i);
    
    
    
        }
    
        /**
         * 编写插值查找算法，要求：数组是有序的
         * @param arr 数组
         * @param left 左边的索引
         * @param right 右边的索引
         * @param findVal 查找的值
         * @return  返回值,找到直接返回，没找到就返回-1
         */
        public static int insertValueSearch(int[] arr,int left,int right, int findVal){
        
            System.out.println("查找次数");
            //在数组中没找到该值，返回-1 比二分查找多了一个条件：判断mid是否越界
            if (left > right || findVal < arr[0] || findVal > arr[arr.length - 1]){
        
                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 {
        
                return mid;
            }
        }
    
    }

**插值查找的注意事项：**

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

2）对于关键字分布不均匀的情况下，该方法不一定比二分查找要好。

#### 本次二分、插入查找教程出自韩顺平的数据结构与算法 ####

[数据结构和算法教程][Link 1]，哔哩哔哩详细教程  
在 78-82p，视频共有五个，不到一个小半时。二倍速30多分钟即可看完。你确定不去听听韩老师的课？

最后，认识一下，我是小白。努力成为一名合格的程序员。期待与你的下次相遇。

[11e2e692979e4e05b714cbb8d2a8d0fb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/962603e7aaa64e15ae00f489fbaed03b.png
[d4cba95a743049a3b1e07c4465771add.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3a8339b613994cb687b863ec310ab893.png
[Link 1]: https://www.bilibili.com/video/BV1E4411H73v?p=71&spm_id_from=pageDriver&vd_source=027fde985896626031abccc06ce8b031