数据查找算法：插值查找

迷南。 2023-02-28 01:22 13阅读 0赞

# 1，插值查找基本介绍 #

*  插值查找的前提条件是目标数组为有序数组
 *  插值查找类似于二分查找，不同的是插值查找每次从自适应middle索引开始查找
 *  插值查找其实就是对二分查找middle索引求值的优化，求值公式为：

> int middle = left + (right - left) \* (target - arr\[left\]) / (arr\[right\] - arr\[left\])

*  二分查找到插值查找的公式演进如下：  
    ![在这里插入图片描述][20200718202038126.png]
 *  举例说明：如果存在一个长度为20， 值为1-20的顺序一维数组，需要查找到1所在的索引。二分查找基本需要查找4次才能查找到；而通过插值查找索引在0位置的数据，只需要一次，即：

> middle = 0 + (19 - 0) \* (1 - 1) / (20 - 1) = 0;  
> arr\[0\] = 1;

# 2，插值查找代码实现 #

package com.self.datastructure.search;
    
    
    /** * 插入查找 * * @author PJ_ZHANG * @create 2020-03-13 15:37 **/
    public class InsertValueSearch { 
    
        public static void main(String[] args) { 
            int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
            System.out.println(insertValueSearch(array, 0, array.length - 1, 10));
        }
    
        /** * 插入查找获取到对应值索引 * @param array 目标数组 * @param left 左索引 * @param right 右索引 * @param target 目标值 * @return */
        public static int insertValueSearch(int[] array, int left, int right, int target) { 
            if (left > right) { 
                return -1;
            }
            // 插入查找, 获取到自适应middle索引
            int middle = left + (right - left) * (target - array[left]) / (array[right] - array[left]);
            System.out.println("middle: " + middle);
            // 大于 向右查找
            if (target > array[middle]) { 
                return insertValueSearch(array, middle + 1, right, target);
            } else if (target < array[middle]) {  // 小于, 向左查找
                return insertValueSearch(array, left, middle - 1, target);
            } else { 
                return middle;
            }
        }
    
    }

# 3，注意事项 #

*  对于数据量较大，关键字分布比较均匀的查找表来说，采用插值查找，速度较快
 *  关键字不均匀的情况下，该方法不一定比二分查找速度快

[20200718202038126.png]: /images/20230209/e0103f735d5448518a224374434344b5.png