首页 > 其他 > 详细

插值查找

时间:2021-09-11 23:45:36      阅读:7      评论:0      收藏:0      [点我收藏+]
//插值查找()
public static void main(String[] args) {
//二分法查找思路:
//插值查找的思路是:不是单纯地通过所有查找都采用二分之一0.5+0.5的比例,这个比例通过查找的值及数组长度和数组首尾大小共同决定
//这个比例为left+(right-left)*(finnalVal-array[left])/(array[right]-array[left])
//这样能更精确得等到对应得值的位置,减少二分查找次数,适用于数组长度长,变化均匀的有序数组
int[] array = new int[1000];
for (int i = 0; i < 1000; i++) {
array[i] = i + 1;
}
int midIndex = array.length / 2;
int finalVal = 300;//待查找的数值
int left = 0;
int right = array.length - 1;
int res = getFinalIndex(array, left, right, finalVal);
System.out.println("下标为:" + res);
}


public static int getFinalIndex(int[] array, int left, int right, int finalVal) {
System.out.println("我跑了一遍");
int midleIndex = (right - left) * (finalVal - array[left]) / (array[right] - array[left]);
//因为此时因为查找的数值、数组头尾差值参与计算,所以midleIndex值很可能不是一个在[left,right)之间的数,所以查找不到的情况要加条件
if (left > right || midleIndex < 0 || midleIndex > array.length - 1) {
return -1;//查找不到值
}
//还是正常往前查找和往后查找
if(array[midleIndex]>finalVal){
right = midleIndex-1;
return getFinalIndex(array, left, right, finalVal);
}else if(array[midleIndex]<finalVal){
left = midleIndex+1;
return getFinalIndex(array, left, right, finalVal);
}else{
return midleIndex;
}
}
在1-1000的数组里查找300,只需要一次就能查到

技术分享图片

 

插值查找

原文:https://www.cnblogs.com/summerZoo/p/15251733.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!