1、插值查找原理介绍

1. 插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。

2. 将折半查找中的求mid 索引的公式 , low 表示左边索引left, high表示右边索引right，key 就是前面我们讲的 findVal

3. int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;/插值索引/ 对应前面的代码公式： int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])

4. 举例说明插值查找算法 1-100 的数组



2、插值查找案例应用

请对一个有序数组进行插值查找 {1,8, 10, 89, 1000, 1234} ，输入一个数看看该数组是否存在此数，并且求出下标，如果没有就提示"没有这个数"。

3、代码实现