php有序表怎么看插值技巧_java实现插值查找

举例解释

package com.zyp.query;/ 插值排序 @author zyp @create 2022/2/22 /public class InsertSearch { public static void main(String[] args){ //待查找数组 int[] array = new int[]{1,2,3,4,5,6,7,8,9,10}; int index = insertQuery(array, 0, array.length - 1, 7); System.out.println("找到的下标为:"+index); } / @param array 待查找数组 @param left 开始查找数据下标 @param right 结束查找数据下标 @param data 查找数据 @return 找到元素所在数组的下标 / public static int insertQuery(int[] array,int left,int right,int data){ //必须要有，否则可能涌现下标越界 if(left > right || data < array[0] || data > array[array.length-1]){ return -1; } / mid值的公式是怎么来的呢 之前二分法我们的mid = (left+right)/2 => left + 1/2(rihjt-left) 这里只是把1/2用(data - array[left])/(array[right]-array[left])更换 / int mid = left + (right - left) (data - array[left]) / (array[right]-array[left]); int midValue = array[mid]; if(data > midValue){ return insertQuery(array, mid + 1, right, data); }else if(data < midValue){ return insertQuery(array, left, mid - 1, data); }else{ return mid; } }}总结

插值查找类似与二分查找。
对付数据量大的以及关键字分布均匀的有序序列来说，插值查找的速率较快。
对付分布不屈均的有序序列来说，该算法不一定比二分查找要好