插值查找法的代码实现（二分查找算法的改进,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);//递归在左半部分查找 } }}测试结果
