内容来自尚硅谷Java数据结构与java算法（Java数据结构与算法）_哔哩哔哩_bilibili

写在前面:本文内容大致和原视频内老师的笔记内容相同，会偶尔插入自己的注释和理解，尽量会完成作业

8.4插值查找算法

插值查找原理介绍：

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

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

1.      int mid = low + (high - low) * (key - arr[low])/ (arr[high] - arr[low]);/*插值索引*/对应前面的代码公式:

int mid = left +(right - left) * (findVal - arr[left])/ (arr[right]- arr[left])

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

8.4.1插值查找应用案例

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

代码实现

8.4.2插值查找的注意事项

1.      对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快

2.      关键字分布不均匀的情况下，该方法不一定比折半查找要好