插值查找法的代码实现（二分查找算法的改进,java语言实现）

简述

对二分查找算法对mid(中间节点)的计算进行改进
使 mid = (low + (high - low) *(val - R[low])/(R[high] - R[low]);
如此，若是被查找的数值的索引在数组的边缘部分查找效率将大大提高；
从测试结果看：查找11 需要查找2次，查找92仅需元查找一次；

实现代码

/**
 * className:Search
 *
 * @author:zjl
 * @version:0.1
 * @date:2020/8/1910:16
 * @since:jdk1.8
 */
public class Search {

    public static void main(String[] args) {
        int R[] = {0,1,11,33,44,59,69,80,86,92,99};
        int i = interpolationSearch(R, 0, R.length - 1, 11);
        System.out.println("11的索引是：" + i);
        System.out.println("--------------------------");
        int i1 = interpolationSearch(R, 0, R.length - 1, 92);
        System.out.println("92的索引是：" + i1);
        System.out.println("--------------------------");
        int i2 = interpolationSearch(R, 0, R.length - 1, 3);
        System.out.println("3的索引是：" + i2);
    }

    /**
     * 插值查找
     * @param R
     * @param low 数组开始索引
     * @param high 数组结束索引
     * @param val 查找的值
     * @return   没有找到返回-1，否则返回对应索引
     */
    public static int interpolationSearch(int[] R, int low, int high, int val) {
        System.out.println("查找一次...");
        float p = val - R[low];
        float q = R[high] - R[low];
        float t = p/q;
        int mid = (int)(low + (high - low) * t);       //与二分查找求中间节点方式不同（改进点）
        if(R[low]>val||R[high]<val)
            return -1;
        if (R[mid] == val) {
            return mid;
        }else if (R[mid] < val) {
            low = mid + 1;
            return interpolationSearch(R, low, high, val);//递归在右半部分查找
        } else {
            high = mid - 1;
            return interpolationSearch(R, low, high, val);//递归在左半部分查找
        }
    }![在这里插入图片描述](https://img-blog.csdnimg.cn/202008191108501.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODMzNDMwNg==,size_16,color_FFFFFF,t_70#pic_center)

}

测试结果