[数据结构与算法]查找算法-插值查找

插值查找原理：

• 插值查找算法类似于二分查找， 不同的是插值查找每次从自适应 mid 处开始查找
• 改变二分查找的区间缩减策略，根据搜索的值来确定区间缩减幅度，使其不再是固定的1/2，这种想法就是“插值查找”
• 如果目标值key和左边界值a[low]差的多，则中间位置mid更靠右；如果目标值key和左边界值差的少，则中间位置mid更靠左。也就是说，插值查找算法的中间位置mid不是真的在中间了，而是根据目标值和边界值的关系动态的确定
  

public class InsertValueSearch {
    public static void main(String[] args) {
        //原始列表,有序且关键字分布均匀
        int[] arr = new int[100];
        for (int i = 0; i < arr.length ; i++) {
            arr[i] = i + 1;
        }
        int target = 26;
        int index = InsertValueSearch(arr, 0, arr.length - 1, target);
        System.out.println(index);  //99
    }

    /**
     * 插值查找算法
     * 注意:插值查找算法也要求列表必须是有序的!!!
     * @param arr    原始列表
     * @param left   每次参与查找的列表的起始元素的下标
     * @param right  每次参与查找的列表的终止元素的下标
     * @param target 最终要查找的目标元素
     * @return 要查找的目标元素在列表中的位置;如果没有找到,则返回-1;
     */
    private static int InsertValueSearch(int[] arr, int left, int right, int target) {
        //如果列表中所有的元素都不匹配,返回-1
        //如果要查找的目标元素大于列表中值最大的元素(即最后一个元素)或者小于值最小的元素(即第一个元素),那么目标元素肯定不存在列表中,直接结束查找;
        //注意:"|| target < arr[0] || target > arr[arr.length - 1]"这段代码是必须要有的,如果没有的话可能会导致后面的mid越界!!!
        if (left > right || target < arr[0] || target > arr[arr.length - 1]) {
            System.out.println("抱歉,列表中并不存在元素:" + target);
            return -1;
        }

        //获取查找点mid,自适应
        //int mid = low + (high - low) * (key - arr[low]) / (arr[high] - arr[low]) ;
        int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
        if (target > arr[mid]) {
            //如果要查找的目标元素大于查找点位置的元素,使用递归对查找点右侧的所有元素进行相同方式的查找
            return InsertValueSearch(arr,  mid + 1, right,target);
        } else if (target < arr[mid]) {
            //如果要查找的目标元素小于查找点位置的元素,使用递归对查找点左侧的所有元素进行相同方式的查找
            return InsertValueSearch(arr,  left, mid - 1,target);
        } else {
            //要查找的目标元素正好就是查找点位置的元素,返回查找点
            return mid;
        }
    }
}