目录

插值查找

基本介绍

插值查找是对二分查找的一种改进,适用于均匀分布的有序表,代码和二分查找一样,有修改的地方就是mid的获取 在二分查找中,${mid=}\frac{low+right}{2}$ 做一些数学变换就变成,${mid=left+}\frac{right-left}{2}$ 也就是说我们的mid每次都是折中的取,但是对于一些均匀分布的有序表,这样做感觉有些费时,比如找字典的时候,找a这个字母,我们肯定不会从中间开始,而是偏向于字典前面一些开始。 插值查找就是基于这样的思想,我们对1/2进行改进 ${mid=}\frac{key-a[left]}{a[right]-a[left]}(right-left)$

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
    /**
     * 插值查找
     *
     * @param arr
     * @param val
     * @return -1表示没找到
     */
    private static int insertSearch(int[] arr, int val) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) * (val - arr[left]) / (arr[right] - arr[left]);
            if (val == arr[mid]) {
                return mid;
            } else if (val < arr[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }

注意事项

  1. 对于数据量较大,关键字分布比较均匀的有序表来说,采用插值查找,速度较快
  2. 关键字分布不均匀的情况下,该方法不一定比折半查找要好