前言

对于有序且均匀分布的数组，插值搜索比二分搜索效果更好。

无论搜索键如何，二分搜索都会转到中间元素进行检查。而插值搜索可能会根据 search-key 到不同的位置。如果 search-key 的值接近最后一个元素，则插值搜索很可能会向末端开始搜索。

给定一个均匀分布值 arr[] 的排序数组，编写一个函数来搜索数组中的特定元素 x。 

线性搜索在 O(n) 时间内找到元素，跳转搜索需要 O(√n) 时间，二分搜索需要 O(Log n) 时间。 插值搜索是对实例的二分搜索的改进，其中排序数组中的值是均匀分布的。

平均而言，插值搜索进行 log(log(n)) 比较（如果元素是均匀分布的），其中 n 是要搜索的元素数。在最坏的情况下（例如键的数值呈指数增长），它可以进行 O(n) 次比较。

算法

除上述划分逻辑外，其余二分算法相同。

• Step1： 在一个循环中，使用探头位置公式计算“pos”的值。
• Step2： 如果匹配，则返回item的索引，退出。
• Step3： 若item小于arr[pos]，计算左子数组的探针位置。否则在右子数组中计算相同。
• Step4： 重复直到找到匹配或子数组减少到零。

Java示例

import java.util.*;
 
class GFG {
 
    // 如果 x 存在于 arr[0..n-1] 中，则返回它的索引，否则返回 -1。
    public static int interpolationSearch(int arr[], int lo,
                                          int hi, int x)
    {
        int pos;
 
        if (lo <= hi && x >= arr[lo] && x <= arr[hi]) {

            pos = lo
                    (((hi - lo) / (arr[hi] - arr[lo]))
                     * (x - arr[lo]));
 
            // 找到目标的条件
            if (arr[pos] == x)
                return pos;
 
            // 如果 x 较大，在右子数组中
            if (arr[pos] < x)
                return interpolationSearch(arr, pos   1, hi,
                                           x);
 
            // 如果 x 较小，在左子数组中
            if (arr[pos] > x)
                return interpolationSearch(arr, lo, pos - 1,
                                           x);
        }
        return -1;
    }
 
    public static void main(String[] args)
    {
 
        // 搜索数组
        int arr[] = { 10, 12, 13, 16, 18, 19, 20, 21,
                      22, 23, 24, 33, 35, 42, 47 };
 
        int n = arr.length;
 
        // 要搜索的元素
        int x = 18;
        int index = interpolationSearch(arr, 0, n - 1, x);
 
        // 如果找到了元素
        if (index != -1)
            System.out.println("索引： "
                                 index);
        else
            System.out.println("没有找到");
    }
}

输出： 索引： 4

性能

二分搜索在一般的情况下时间复杂度是对数时间，进行O(log n)次比较操作。

插值搜索的最坏时间复杂度是O(n)，平均进行O(log(log n))次比较操作。因为用插值公式计算搜索键值，能使搜索范围比二分法更快缩小。所以除非输入数据数量很少，否则插值搜索比二分搜索与线性搜索更快，但数组必须事先被排序。无论对任何大小的输入数据，插值搜索算法使用的空间复杂度一样是O(1)。

这篇好文章是转载于：学新通技术网