数据结构与算法——插值查找算法实现

插值查找算法

与二分查找的不同点
原理：int mid = (high-low) / 2;//二分查找
     int mid = (high - low) * (findVal - arr[low]) / (arr[high] - arr[low]);//插值查找
至于为什么这个公试会比较快，欢迎*大的朋友给我上上课

算法实现

public class InsertValueSearchDemo {
    public static void main(String[] args) {
        int[] arr = new int[100];
        for (int i = 0; i < 100; i++) {
            arr[i] = i;
        }
        System.out.println(InsertValueSearch(arr, 0, 99, 2));
    }

    /**
     * 优化
     * 递归的二分查找，查找可能有多个相同值
     * 时间复杂度: log2n
     * 有点像二叉排序树的查找
     *
     * 思路：找到第一个，往它的左边遍历，右边遍历时再添加
     * @param arr 待查找数组,有序
     * @param low
     * @param high
     * @param findVal 待找值
     * @return 待找值的下标，没有返回-1
     */
    public static ArrayList<Integer> InsertValueSearch(int[] arr, int low, int high, int findVal){
        System.out.println("插值查找——");
        //说明没找到值
        //防止数组越界
        if (low > high || findVal < arr[low] || findVal > arr[high] ){
            return new ArrayList<>();
        }
        //比较值,与二分查找不同的地方
        //也是插值查找的关键
        //int mid = (high-low) / 2;
        int mid = (high - low) * (findVal - arr[low]) / (arr[high] - arr[low]);
        //在右边找
        if (findVal > arr[mid]){
            return InsertValueSearch(arr,mid+1,high,findVal);
        }
        //在左边找
        else if (findVal < arr[mid]){
            return InsertValueSearch(arr,low,mid-1,findVal);
        }
        //上面都不成立，则找到值
        else {
            ArrayList<Integer> resIndexList = new ArrayList<>();
            //遍历左边的临时变量
            int temp = mid-1;
            while (true){
                //数组已经越界
                if (temp < 0 || arr[temp] != findVal ){
                    break;
                }
                temp --;
            }
            //向右扫面,并且加入，这样，下标就是有序的
            temp = temp + 1;
            while (true){
                if (temp > arr.length-1 || arr[temp] != findVal){
                    break;
                }
                resIndexList.add(temp);
                temp ++ ;
            }
            return resIndexList;
        }
    }

ps： 插值查找算法再数据没那么平均分布的情况下，效率不一定比二分查找效率高