查找算法----插值查找

package 查找算法; public class InterpolationSrarch { public static void main(String[] args) { int arr[]={1,5,12,21,30,32,55,68,80,89,90,99}; int key=30; int index=interpolationSrarch(arr,key,0,arr.length-1); System.out.println("index="+index); } private static int interpolationSrarch(int[] arr, int key, int low, int high) { if(low>high){ return -1; } int mid=low+(int)(1.0*(key-arr[low])/(arr[high]-arr[low])*(high-low)); if (mid<low||mid>high){ return -1; } if(arr[mid]==key){ return mid; }else if (arr[mid]>key){ return interpolationSrarch(arr,key,low,mid-1); }else { return interpolationSrarch(arr,key,mid+1,high); } } }

执行结果

index=4