//二分查找的前提是数组是有序的
public class BinarySort {
    public static void main(String[] args) {
        int[] arr={1,2,2,2,34,67,88,123};
        List<Integer> integers = binarySort2(arr, 0, arr.length - 1, 2);
        Collections.sort(integers);  //对list集合中元素进行排序后输出
        System.out.println(integers); //（list集合特点：有序可重复指的是输出顺序与插入顺序一致，不是数字之间的大小顺序）
        /*int i = binarySort(arr, 0, arr.length - 1, 2);
        System.out.println(i);*/
    }

    /**二分查找（此方法参数一定要传入左右下标，因为需要递归进行局部遍历，左右下标会动态变化）
     * @param arr  传入待查找数组
     * @param left  待比较数组的左下标
     * @param right  待比较数组的右下标
     * @param findVal 待查找值
     */
    public static int binarySort(int[] arr,int left,int right,int findVal){
         if(right < left){  //遍历完数组，没有找到符合值
             return -1;
         }
         int mid=(left+right)/2;  //求出中间值下标
        int midValue=arr[mid];  //求出中间值
        if (findVal >midValue){  //比中间值大，向右递归
            return binarySort(arr,mid+1,right,findVal);
        }else if (findVal < midValue){
            return binarySort(arr,left,mid-1,findVal);
        }else {
            return mid;  //找到
        }
    }

    /**增加条件：查找所有满足条件的元素坐标
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static List<Integer> binarySort2(int[] arr, int left, int right, int findVal){
        ArrayList<Integer> indexs = new ArrayList<>();
        if(right < left){  //遍历完数组，没有找到符合值
            return indexs;
        }
        int mid=(left+right)/2;  //求出中间值下标
        int midValue=arr[mid];  //求出中间值
        if (findVal >midValue){  //比中间值大，向右递归
            return binarySort2(arr,mid+1,right,findVal);
        }else if (findVal < midValue){
            return binarySort2(arr,left,mid-1,findVal);
        }else {
            /*课后思考题： {1,8, 10, 89, 1000, 1000，1234} 当一个有序数组中，
             * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
             * 思路分析
             * 1. 在找到 mid 索引值，不要马上返回
             * 2. 向 mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合 ArrayList
             * 3. 向 mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合 ArrayList
             * 4. 将 Arraylist 返回*/
            //向左查找
            int i=mid-1;
            while (true){
                if (i<0 || arr[i] != findVal){  //因为二分查找法是针对有序的数，如果midVal值符合，
                    break;            //则其他几个数也在临近的位置（要么就查找完毕要么就没有了退出循环），
                }                       //所以后面的阶数条件是arr[i] !=midVal
                indexs.add(i);
                i--;
            }
            indexs.add(mid);  //此时的中间值符合别忘了放入集合中
            //向右查找
             i=mid+1;
            while (true){
                if (i>arr.length-1 || arr[i] != findVal){
                    break;
                }
                indexs.add(i);
                i++;
            }
            return indexs;  //返回集合
        }
    }

}

8.3插值查找算法


8.3.1插值查找应用实例
@请对一个有序数组进行插值查找 ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。

//插值查找也是适应有序的数组
public class InsertValueSort {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i=0;i<100;i++){
            arr[i]=i;
        }
        int i = insertValueSort(arr, 0, arr.length - 1, 10);
        System.out.println(i);
    }

    /**
     * @param arr  待查找数组
     * @param left  待查找数组的左边边界索引
     * @param right  待查找数组的右边边界索引
     * @param findNum 待查找的数
     * @return
     */
    public static int insertValueSort(int[] arr,int left,int right,int findNum){
        //System.out.println("----");
        //findNum<arr[0] || findNum>arr[arr.length-1]条件不仅是优化，而且是必要条件
        //防止后面的arr[mid]数组越界（倘若findNum非常大）
        if (left>right || findNum<arr[0] || findNum>arr[arr.length-1]){
            return -1;
        }
        //插值算法求mid
        int mid=left+(right-left)*(findNum-arr[left])/(arr[right]-arr[left]);
        int midValue=arr[mid];
        if (findNum<midValue){  //如果小于就往左边循环
            return insertValueSort(arr,left,mid-1,findNum);
        }else if (findNum>midValue){
            return insertValueSort(arr,mid+1,right,findNum);
        }else {
            return mid;
        }
    }
}