插值查找算法

一、插值查找算法基本思想

插值查找是一种在有序数组（前提条件）中查找某一特定元素的查找算法。插值查找基于二分查找**，不同的是插值查找每次从自适应mid处开始查找**，提高查找效率。

二分查找查找点和插值查找查找点计算如下：

其中key为待查找元素，low为待查找区间左端，high为待查找区间右端，mid为自适应查找点。
插值查找将上述的比例参数1/2改进为自适应，根据待查找元素在整个有序数组中所处的位置，使mid值的变化更靠近待查找元素key，可以间接地减少了比较次数。

二、代码实现

1、递归方式

package Search;

import java.util.Arrays;
import java.util.Scanner;

public class InsertValueSearch {
	public static int insertvaluesearch(int arr[],int value,int low,int high) {
		while(low<=high) {
			int mid=low+(high-low)*(value-arr[low])/(arr[high]-arr[low]);//插值查找中间索引公式
			if(arr[mid]==value) {//若中间位置值等于我们所需要查找值，即返回中间值
				return mid;
			}
			if(arr[mid]<value) {//若中间位置值小于我们所需查找值，则向右递归且将下界值变为mid+1
				return insertvaluesearch(arr,value,mid+1,high);
			}
			if(arr[mid]>value) {//若中间位置值大于我们所需查找值，则向左递归将上界值变为mid-1
				return insertvaluesearch(arr,value,low,mid-1);
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		int[] arr= {31,17,5,47,11,33,3,19,13,59,1,43,41,37,7,53,29};
		Arrays.sort(arr);//采用插值查找时，需要对该数组进行排序
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入查找元素：");
		int value=sc.nextInt();
		System.out.printf("查找元素 %d 的位置是 %d ",value,insertvaluesearch(arr,value,0,arr.length-1));
	}
}

运行结果：

请输入查找元素：
37
查找元素 37 的位置是 11

2、非递归方式

package Search;

import java.util.Arrays;
import java.util.Scanner;

public class InsertValueSearch {
	public static int insertvaluesearch(int arr[],int value) {
		int low=0;//指针low表示待查元素所在范围的下界，下界索引从0开始
		int high=arr.length-1;//指针high表示待查元素所在范围的上界
		while(low<=high) {
			int mid=low+(high-low)*(value-arr[low])/(arr[high]-arr[low]);//插值查找中间索引公式
			if(arr[mid]==value) {//若中间位置值等于我们所需要查找值，即返回中间值
				return mid;
			}
			if(arr[mid]<value) {//若中间位置值小于我们所需查找值，则向右递归且将下界值变为mid+1
				low=mid+1;
			}
			if(arr[mid]>value) {//若中间位置值大于我们所需查找值，则向左递归将上界值变为mid-1
				high=mid-1;
			}
		}
		return -1;
	}
	public static void main(String[] args) {
		int[] arr= {31,17,5,47,11,33,3,19,13,59,1,43,41,37,7,53,29};
		Arrays.sort(arr);//采用插值查找时，需要对该数组进行排序
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入查找元素：");
		int value=sc.nextInt();
		System.out.printf("查找元素 %d 的位置是 %d ",value,insertvaluesearch(arr,value));
	}
}

运行结果：

请输入查找元素：
43
查找元素 43 的位置是 13 

三、插值查找算法的注意事项

（1）对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找时速度较快。
（2）在关键字分布不均匀的情况下，插值查找不一定比折半查找好。