二分查找、折半查找（Java）-蒲公英云

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，就需要退出

代码实现

在这里插入图片描述

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表示右边索引。

在这里插入图片描述

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

你可以把上面两条公式的（ 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;
        }
    }
}