插值查找算法图文详解

插值查找算法又称插值搜索算法，是二分查找算法的改进版。

和二分查找算法相同，插值查找算法也仅适用于有序序列。此外，当有序序列中的元素呈现均匀分布时，插值查找算法的执行效率比二分查找算法更高。也就是说，插值查找算法适用于均匀分布的有序序列。

所谓均匀分布，简单地理解就是：序列中各个相邻元素的差值近似相等。例如 {0,10,20,30,40} 就是一个均匀分布的有序序列，序列中各个相邻元素的差值都为 10；{0,1,100,200,10000} 是一个有序序列，但序列中的元素并不符合均匀分布的特征。

插值查找算法的基本原理

讲解插值查找算法之前，我们先简单回忆一下二分查找算法的查找过程。

例如，在{1,2,3,4,5,6,7,8,9,10}序列中查找元素 2，二分查找算法的查找过程如下图所示：

图 1 二分查找算法的查找过程

二分查找算法会先找到搜索区域内的中间元素，然后和目标元素进行匹配，如果匹配失败，则选取中间元素左侧或右侧的区域作为新的搜索区域，继续以同样的方法查找目标元素。

插值查找算法的查找过程和二分查找算法非常相似，唯一的不同之处在于，该算法并没有采取“等分搜索区域”的方式，而是通过如下公式计算出“中间元素”的位置：

mid = Lo + ( (Hi - Lo) / (A[Hi] - A[Lo]) ) * (X - A[Lo])

其中各个选项的含义为：

• mid：表示要求的中间值的位置；

• Lo：表示查找区域中首个元素所在的位置；

• Hi：表示查找区域中最后一个元素所在的位置；

• X：表示要查找的目标元素的值；

• A[]：表示待搜索的有序序列。

也就是说，插值查找算法首先会以此公式计算出“中间元素”的位置，然后同目标元素进行匹配，如果匹配失败，则会选取“中间元素”左侧或右侧的区域作为新的搜索区域，继续以同样的方式查找目标元素。

仍以图 1 中的有序序列为例，该序列为均匀分布的有序序列，如果使用插值查找算法查找元素 2，则查找过程如下所示：

1) 首先通过公式求得“中间值”：

mid = 1 + ( (10-1)/(10-1) ) * (2-1) = 2

也就是说，该算法首先以第 2 个元素作为“中间元素”，如下图所示：

图 2 插值查找算法的查找过程
 

显然，该值即为要查找的目标元素，查找成功。

如下为实现插值查找算法的伪代码：

输入 arr[]                                                 // 输入有序序列
输入 ele                                                   // 输入查找的目标元素   
binary_search( arr , p , q , ele):               // [p,q] 指定搜索区域，ele 为要搜搜的目标元素
    if p > q:                                              // [p,q] 不存在时，返回一个错误值（比如 -1）
        return -1
    mid <- p + ( (q-p)/(arr[q] - arr[p]) * (ele - arr[p]) )    // 找到 [p,q] 区域“中间值”的下标
    if ele == arr[mid]:                                    // 递归的出口，即 ele 和中间元素的值相等
        return mid
    if ele ＜ arr[mid]:                                    // 比较 ele 和中间元素的值，进一步缩小搜索区域
        return binary_search(arr , p , mid-1 , ele)
    else:
        return binary_search(arr , mid+1 , q , ele)

插值查找算法的具体实现

如下为实现插值查找算法的 C 语言程序：

#include <stdio.h>
//实现插值查找算法，ele 表示要查找的目标元素，[p,q] 指定查找区域
int interpolation_search(int *arr, int p, int q, int ele) {
    int mid = 0;
    //如果[p,q] 不存在，返回 -1
    if (p > q) {
        return -1;
    }
    // 找到"中间元素"所在的位置
    mid = p + ((q - p) / (arr[q] - arr[p]) * (ele - arr[p]));
    //递归的出口
    if (ele == arr[mid]) {
        return mid;
    }
    //比较 ele 和 arr[mid] 的值，缩小 ele 可能存在的区域
    if (ele < arr[mid]) {
        //新的搜索区域为 [p,mid-1]
        return interpolation_search(arr, p, mid - 1, ele);
    }
    else {
        //新的搜索区域为 [mid+1,q]
        return interpolation_search(arr, mid + 1, q, ele);
    }
}

int main()
{
    int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
    //输出元素 2 所在位置的下标
    int pos = interpolation_search(arr, 0, 9, 2);
    if (pos != -1) {
        printf("%d", interpolation_search(arr, 0, 9, 2));
    }
    else {
        printf("查找失败");
    }
   
    return 0;
}

如下为实现插值查找算法的 Java 程序：

public class Demo {
    // 实现插值查找算法，ele 表示要查找的目标元素，[p,q] 指定查找区域
    public static int interpolation_search(int[] arr, int p, int q, int ele) {
        // 如果[p,q] 不存在，返回 -1
        if (p > q) {
            return -1;
        }
        // 找到中间元素所在的位置
        int mid = p + ((q - p) / (arr[q] - arr[p]) * (ele - arr[p]));
        // 递归的出口
        if (ele == arr[mid]) {
            return mid;
        }
        // 比较 ele 和 arr[mid] 的值，缩小 ele 可能存在的区域
        if (ele < arr[mid]) {
            // 新的搜索区域为 [p,mid-1]
            return interpolation_search(arr, p, mid - 1, ele);
        } else {
            // 新的搜索区域为 [mid+1,q]
            return interpolation_search(arr, mid + 1, q, ele);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        // 输出目标元素 2 所在位置的下标
        int add = interpolation_search(arr, 0, 9, 2);
        if(add != -1) {
            System.out.print(add);
        }else {
            System.out.print("查找失败");
        }
       
    }
}

如下为实现插值查找算法的 Python 程序：

#实现插值查找算法，ele 表示要查找的目标元素，[p,q] 指定查找区域
def interpolation_search(arr,p,q,ele):
    #如果[p,q] 不存在，返回 -1
    if p > q:
        return -1
    #找到中间元素所在的位置
    mid = int(p + ((q - p) / (arr[q] - arr[p]) * (ele - arr[p])))
    #递归的出口
    if ele == arr[mid]:
        return mid
    #比较 ele 和 arr[mid] 的值，缩小 ele 可能存在的区域
    if ele < arr[mid]:
        return interpolation_search(arr,p,mid-1,ele)
    else:
        return interpolation_search(arr,mid+1,q,ele)

arr = [1,2,3,4,5,6,7,8,9,10]
#输出元素 2 所在位置的下标
add = interpolation_search(arr, 0, 9, 2);
if add != -1:
    print(add)
else:
    print("查找失败")

以上程序的输出结果均为：

1