（1）插值查找原理介绍：
插值查找算法类似于二分查找，不同的是插值查找每次从自适应mid处开始查找。
（2）将折半查找中的求mid索引的公式，low表示左边索引left,hight表示右边索引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的数组
插值查找算法的 举例说明 > > 数组 arr = [1, 2, 3, ......., 100] > > 假如我们需要查找的值 1 > > 使用二分查找的话，我们需要多次递归，才能找到 1 > > 使用插值查找算法 > > int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left]) > > int mid = 0 + (99 - 0) * (1 - 1)/ (100 - 1) = 0 + 99 * 0 / 99 = 0 > > 比如我们查找的值 100 > > int mid = 0 + (99 - 0) * (100 - 1) / (100 - 1) = 0 + 99 * 99 / 99 = 0 + 99 = 99
插值查找应用案例
请对一个有序数组进行插值查找{1,8,10,89,1000,1234},输入一个数看看该数组是否有此数，并且求出下标，如果没有就提示“没有这个数”。
代码实现
public class InsertValueSearch {
public static void main(String[] args) {
int arr[]={1,8,10,89,1000,1000,1234};
int index = insertValueSearch(arr,0,arr.length-1,1234);
System.out.println("index="+index);
}
public static int insertValueSearch(int[] arr,int left,int right,int findVal){
System.out.println("插值查找次数~");
//注意：findVal<arr[0] 和 findVal>arr[arr.length-1]必须需要
//否则我们得到的mid可能越界
if(left>right||findVal<arr[0]||findVal>arr[arr.length-1]){
return -1;
}
//求出mid,自适应
int mid=left+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]);
int midVal=arr[mid];
//当left > right时，说明递归整个数组，但是没找到
if(left>right){
return -1;
}
if(findVal > midVal){//向右递归
return binarySearch(arr,mid+1,right,findVal);
}else if(findVal < midVal){
return binarySearch(arr,left,mid-1,findVal);
}else{
return mid;
}
}
}
运行结果
插值查找次数~
index=6
插值查找注意事项：
（1）对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找。
（2）关键字分布不均匀的情况下，该方法不一定比折半查找要好
Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。
它的内容包括：
- 大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
- 原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
- 持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
- 覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
- 不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
- 宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
- 宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
- 宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw
目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：
想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询
同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】 即可免费领取。
