插值查找算法

要求数组也是有序的，相比于折半查找（二分查找）来说，只是mid的计算方法不一样。

Int mid=left+(right-left)*(val-arr[left])/(arr[right]-arr[left])

插值查找注意事项：

1. 对于数据量较大，关键字（数组的值跳跃很大）分布比较均匀的查找表来说，采用插值查找，速度较快
2. 关键字分布不均匀的情况下，该方法不一定比折半查找要好

代码实现如下：

package com.atguigu.serach;

import java.util.Arrays;

public class InsertValueSort {

	public static void main(String[] args) {
		int[] arr=new int[100];
		for(int i=0;i<100;++i) {
			arr[i]=i+1;
		}
		int index=insertValueSearch(arr, 0, arr.length-1, 100);
		if(index==-1) {
			System.out.println("未找到此值");
		}
		else {
			System.out.println("找到的值在数组中的索引是"+index);
		}
	}
	
	//插值查找算法
	/**
	 * @param arr  待查找数组(数组有序)
	 * @param left 左索引
	 * @param right 右索引
	 * @param val   查找的值
	 * @return
	 */
	public static int insertValueSearch(int[] arr,int left,int right,int val) {
		//arr[0]<=val&&arr[arr.length-1]>=val用来保护数组不越界
		while(left<=right&&arr[0]<=val&&arr[arr.length-1]>=val) {
			int mid=left+(right-left)*(val-arr[left])/(arr[right]-arr[left]);
			if(arr[mid]<val) {//val应该在arr[mid]右边,left右移
				left=mid+1;
			}
			else if(arr[mid]>val) {//val应该在arr[mid]左边,right左移
				right=mid-1;
			}
			else {
				return mid;
			}
		}
		return -1;
	}

}