插值查找法又称为插补查找法，是二分查找法的改进版，按照数据位置的分布，利用公式预测数据所在的位置，再以二分法的方式渐渐逼近。使用插值查找法时，假设数据平均分布在数组中，而每一项数据的差距相当接近或有一定的距离比例。插值查找法的公式为：

mid=low+((key-data[low])/(data[high]-data[low]))*(high-low)

其中，key是要查找的键值，data[high]、data[low]是剩余待查找记录中的最大值和最小值。假设数据项数为n，其插值查找法的步骤如下：

（1）将记录从小到大的顺序给予1、2、3、...、n的编号。

（2）令low=1，high=n。

（3）当low<high时，重复执行步骤4和步骤5

（4）令mid=low+((key-data[low])/(data[high]-data[low]))*(high-low)

（5）若key<且high！=mid=-1，则令high=mid=-1

（6）若key=,则表示成功查找到键值的位置

（7）若key>且low！=mid+1，则令low=mid+1

算法分析：

（1）一般而言，差值查找法优于顺序查找法，数据分布越平均，查找速度越快，甚至可能第一次就找到数据。插值查找法的时间复杂度取决于数据分布的情况，平均而言优于O（）。

（2）使用插值查找法的数据需先经过排序。

package DateStructures.Queue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author admin $
 * @title $mid=low+((key-data[low])/(data[high]-data[low]))*(high-low)
 *
 * 其中，key是要查找的键值，data[high]、data[low]是剩余待查找记录中的最大值和最小值。假设数据项数为n
 * @description $
 * @updateTime $ 20:11$ $
 * @throws $
 */
public class InterSearch {
    public static void main(String[] args) throws IOException {
        int val=1,num;
        int data[]=new int[50];
        String StrM;
        BufferedReader keyin=new BufferedReader(new InputStreamReader(System.in));
        for (int i=0;i<50;i++){
            data[i]=val;
            val+=((int )(Math.random()*100)%5+1);
        }
        while (true){
            num=0;
            System.out.println("输入查找的键值，输入-1结束");
            StrM=keyin.readLine();
            val=Integer.parseInt(StrM);
            if (val==-1)break;
            num=interpolation(data,val);
            if (num ==-1) {
                System.out.println("没有找到");
            }
            else System.out.println("在第"+(num+1)+"个位置找到["+data[num]+"]");
        }


    }
    public static int interpolation(int data[],int val){
        int low,mid,high;
        low=0;
        high=49;
        int tmp;
        while (low <= high && val != -1) {

            tmp=(int)((float)(val-data[low])*(high-low)/(data[high]-data[low]));
            mid=low+tmp;
            if (mid>50||mid<-1) return -1;
            if (val<data[low]&&val<data[high]) return -1;
            else if(val>data[low]&&val>data[high]) return -1;
            if (val==data[mid]) return mid;
            else if(val<data[mid]){
                high=mid-1;
            }
            else  if(val>data[mid]){
                low=mid+1;
            }
        }
        return -1;
    }
}

打印输出：