java数据结构-插值查找-爱代码爱编程
1、插值查找:实现的是利用公式进行,更好地调整靠近查找目标值
公式:
left +(right -left) *(findVal-arr[left])/ (arr[right]-arr[left])
import java.util.Arrays;
/*
插值查找
*/
public class InsertValueSearch {
public static void main(String[] args){
// 创建一个数组
/*
int[] arr = new int[100];
for (int i = 0; i < 100; i++) {
arr[i] = i+1;
}*/
// int[] arr = {1,5,7,16,99,100};
int[] arr = {1,8,10,89,89,1000,1234};
// System.out.println(Arrays.toString(arr));
int index = insertValueSearch(arr,0,arr.length-1,1000);
System.out.println("index = "+index);
}
// 编写插值查找算法
// 要求数组也是有序的
public static int insertValueSearch(int[] arr,int left,int right,int findVal){
System.out.println("查找次数");
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 midVal = arr[mid];
if(findVal > midVal){
// 说明向右边递归
return insertValueSearch(arr,mid+1,right,findVal);
} else if (findVal<midVal) {
return insertValueSearch(arr,left,mid-1,findVal);
}else{
return mid;
}
}
}