插值查找

//插值查找（）
public static void main(String[] args) {
    //二分法查找思路：
    //插值查找的思路是：不是单纯地通过所有查找都采用二分之一0.5+0.5的比例，这个比例通过查找的值及数组长度和数组首尾大小共同决定
    //这个比例为left+(right-left)*(finnalVal-array[left])/(array[right]-array[left])
    //这样能更精确得等到对应得值的位置，减少二分查找次数,适用于数组长度长，变化均匀的有序数组
    int[] array = new int[1000];
    for (int i = 0; i < 1000; i++) {
        array[i] = i + 1;
    }
    int midIndex = array.length / 2;
    int finalVal = 300;//待查找的数值
    int left = 0;
    int right = array.length - 1;
    int res = getFinalIndex(array, left, right, finalVal);
    System.out.println("下标为：" + res);
}


public static int getFinalIndex(int[] array, int left, int right, int finalVal) {
    System.out.println("我跑了一遍");
    int midleIndex = (right - left) * (finalVal - array[left]) / (array[right] - array[left]);
    //因为此时因为查找的数值、数组头尾差值参与计算，所以midleIndex值很可能不是一个在[left，right)之间的数,所以查找不到的情况要加条件
    if (left > right || midleIndex < 0 || midleIndex > array.length - 1) {
        return -1;//查找不到值
    }
    //还是正常往前查找和往后查找
    if(array[midleIndex]>finalVal){
        right = midleIndex-1;
       return getFinalIndex(array, left, right, finalVal);
    }else if(array[midleIndex]<finalVal){
        left = midleIndex+1;
        return getFinalIndex(array, left, right, finalVal);
    }else{
        return  midleIndex;
    }
}
在1-1000的数组里查找300，只需要一次就能查到

插值查找

原文：https://www.cnblogs.com/summerZoo/p/15251733.html