查找–插值查找(Java)
博客说明
文章所涉及的资料来自互联网整理和个人总结,意在于个人学习和经验汇总,如有什么地方侵权,请联系本人删除,谢谢!
介绍
插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。
自适应
计算自适应mid
int mid = left + (right – left) * (findVal – arr[left]) / (arr[right] – arr[left])
代码
package cn.guizimo.search;
public class InsertValueSearch {
public static void main(String[] args) {
int max = 100;
int[] arr = new int[max];
for (int i = 0; i < max; i++) {
arr[i] = i + 1;
}
int index = insertValueSearch(arr, 0, arr.length - 1, 100);
if(index == -1){
System.out.println("未找到");
}else {
System.out.println("下标为:"+index);
}
}
public static int insertValueSearch(int[] arr, int left, int right, int value) {
if (left > right || value < arr[0] || value > arr[arr.length - 1]) {
return -1;
}
int mid = left + (right - left) * (value - arr[left]) / (arr[right] - arr[left]);
int midValue = arr[left];
if (value > arr[mid]) {
return insertValueSearch(arr, mid + 1, right, value);
} else if (value < arr[mid]) {
return insertValueSearch(arr, left, mid - 1, value);
} else {
return mid;
}
}
}
注意的事项
- 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找, 速度较快.
- 关键字分布不均匀的情况下,该方法不一定比折半查找要好
感谢
尚硅谷
万能的网络
以及勤劳的自己
原文
https://segmentfault.com/a/1190000023059396
本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 查找–插值查找(Java)