java实现插值查找算法
插值查找算法原理介绍:
1.插值查找算法类似于二分查找,不同的是插值查找每次从自适应mid处开始查找。
2.将折半查找中的求mid索引的公式进行优化,key 代表查找的值findValue
公式为:int midIndex = left + (right- left ) * (key - arr[left ]) / (arr[right]- arr[left ]);对应代码:int mid=left +(right-left)*(findval-arr[left])/(arr[right]-arr[left]);
插值查找注意事项
在元素数值均匀分布的有序数组里面, 用这种方法查找是很快的。特别的,对绝对均匀分布的数组(相邻元素差值相同), 插值查找用一次比较就能查找成功:
当然了, 前提是数组中元素数值是均匀分布的, 如果是对 1,2,40,99,1000 这种分布很不均匀的数组, 插值查找的计算会起到反效果, 就不如二分查找了
时间复杂度:O(logn)
java代码实现
//插值查找算法,也要求是有序的。
public class InsertValueSearch {
public static void main(String[] args) {
int[] arr = {0, 10, 20, 21, 23, 56, 75, 99, 100};
int result = insertValueSearch(arr, 0, arr.length - 1, 99);
if (result != -1) {
System.out.println("结果为:" + result);
} else {
System.out.println("没有找到对应的结果。");
}
}
/**
* 插值查找算法
*
* @param arr 待查找的数组
* @param left 待查找数组的左边
* @param right 待查找数组的右边
* @param findval 带查找的数
* @return 若找到就返回 对应的下标,若没有找到就返回-1.
*/
public static int insertValueSearch(int[] arr, int left, int right, int findval) {
if (left > right || findval < arr[0] || findval > arr[arr.length - 1]) {
return -1;
}
int mid = left + (right - left) * (findval - arr[left]) / (arr[right] - arr[left]);
int find = arr[mid];
if (findval < find) {
return insertValueSearch(arr, left, mid - 1, findval);
} else if (findval > find) {
return insertValueSearch(arr, mid + 1, right, findval);
} else {
return mid;
}
}
}