插值查找

介绍

插值查找.插值查找的思想：基于数组的有序性，从数组开头开始查找，根据插值公式 $\frac{value - array[start]} {array[end] - array[start]}$ ,将要查找的关键字 value 与 查找数组中的最大、最小记录的关键字比较的查找方法

特点：

• 中间索引值公式：middle = start + $\frac{value - array[start]} {array[end] - array[start]}$ * (end - start)

实现

/**
 * @description: [start,end] 查找 value

                 1. 首先确定 array 自适应插值索引 middle:

                    middle = start + (end - start) * (value - array[start]) / (array[end] - array[start])

                 2.

                 3. 
 */

function InsertionSearch(array, start, end, value) {
    if (start > end || value < array[start] || value > array[end]) {
        return -1;
    }
    let middle =
        start +
        ((value - array[start]) * (end - start)) /
        (array[end] - array[start]);
    let middleValue = array[middle];
    if (value > middleValue) {
        return InsertionSearch(array, middle + 1, end, value);
    } else if (value < middleValue) {
        return InsertionSearch(array, start, middle - 1, value);
    } else {
        return middle;
    }
}

const array = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
console.log(InsertionSearch(array, 0, array.length - 1, 80));
console.log(array[InsertionSearch(array, 0, array.length - 1, 80)]);