插值查找算法

插值查找算法又称插值搜索算法，是在二分查找算法的基础上改进得到的一种查找算法。

插值查找算法只适用于有序序列，换句话说，它只能在升序序列或者降序序列中查找目标元素。作为“改进版”的二分查找算法，当有序序列中的元素呈现均匀分布时，插值查找算法的查找效率要优于二分查找算法；反之，如果有序序列不满足均匀分布的特征，插值查找算法的查找效率不如二分查找算法。

所谓均匀分布，是指序列中各个相邻元素的差值近似相等。例如，{10, 20, 30, 40, 50} 就是一个均匀分布的升序序列，各个相邻元素的差值为 10。再比如 {100, 500, 2000, 5000} 是一个升序序列，但各相邻元素之间的差值相差巨大，不具备均匀分布的特征。

插值查找算法的解题思路

对于已经学过二分查找算法的读者来说，学习插值查找算法会变得非常容易，因为插值查找算法完全照搬了二分查找算法的解题思路，仅对一些实现细节做了修改。

首先，我们通过一个实例回忆一下二分查找算法的解题思路。例如，在 {1,2,3,4,5,6,7,8,9,10} 升序序列中查找元素 2，二分查找算法的查找过程如下图所示：


如图 1 所示，先找到搜索区域中的中间元素，然后和目标元素进行比较，如果相同表示查找成功；反之，根据比较结果选择中间元素左侧或右侧的区域作为新的搜索区域，以同样的方式继续查找。

插值查找算法的解题思路和二分查找算法几乎相同，唯一的区别在于，每次与目标元素做比较的元素并非搜索区域内的中间元素，此元素的位置需要通过如下公式计算得出：

Mid = Begin + ( (End - Begin) / (A[End] - A[Begin]) ) * (X - A[Begin])

式子中，各部分的含义分别是：

• Mid：计算得出的元素的位置；
• End：搜索区域内最后一个元素所在的位置；
• Begin：搜索区域内第一个元素所在的位置；
• X：要查找的目标元素；
• A[]：表示整个待搜索序列。

为了方便讲解，我们仍将 Mid 位置上的元素称为 "中间元素"。

使用插值查找算法在 {1,2,3,4,5,6,7,8,9,10} 升序序列中查找元素 2，查找过程如下：
1) 假设序列中各个元素的位置为 0~9，搜索区域为整个序列，通过公式计算出 "中间元素" 的位置：

Mid = 0 + ( (9-0)/(10-1) ) * (2-1) = 1

"中间元素" 的位置为 1，也就是元素 2，显然这是我们要找的目标元素，查找结束。整个查找过程如下所示：


对比图 1 和图 2 不难看出，在 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 这个满足均匀分布的升序序列中查找元素 2，插值查找算法的执行效率要优于二分查找算法。

插值查找算法的具体实现

如下用伪代码给大家展示了插值查找算法的具体实现过程：

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

结合伪代码，如下是使用插值查找算法在 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 序列中查找元素 2 的 C 语言程序：

#include <stdio.h>
//实现插值查找算法，ele 表示要查找的目标元素，[begin,end] 指定查找区域
int interpolation_search(int* arr, int begin, int end, int ele) {
    int mid = 0;
    //如果[begin,end] 不存在，返回 -1
    if (begin > end) {
        return -1;
    }
    //如果搜索区域内只有一个元素，判断其是否为目标元素
    if (begin == end) {
        if (ele == arr[begin]) {
            return begin;
        }
        //如果该元素非目标元素，则查找失败
        return -1;
    }
    // 找到"中间元素"所在的位置
    mid = begin + ((end - begin) / (arr[end] - arr[begin]) * (ele - arr[begin]));
    //递归的出口
    if (ele == arr[mid]) {
        return mid;
    }
    //比较 ele 和 arr[mid] 的值，缩小 ele 可能存在的区域
    if (ele < arr[mid]) {
        //新的搜索区域为 [begin,mid-1]
        return interpolation_search(arr, begin, mid - 1, ele);
    }
    else {
        //新的搜索区域为 [mid+1,end]
        return interpolation_search(arr, mid + 1, end, 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;
}

如下是使用插值查找算法在 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 序列中查找元素 2 的 Java 程序：

public class Demo {
    // 实现插值查找算法，ele 表示要查找的目标元素，[begin,end] 指定查找区域
    public static int interpolation_search(int[] arr, int begin, int end, int ele) {
        // 如果[begin,end] 不存在，返回 -1
        if (begin > end) {
            return -1;
        }

        //如果搜索区域内只有一个元素，判断其是否为目标元素
        if (begin == end) {
            if (ele == arr[begin]) {
                return begin;
            }
            //如果该元素非目标元素，则查找失败
            return -1;
        }

        // 找到中间元素所在的位置
        int mid = begin + ((end - begin) / (arr[end] - arr[begin]) * (ele - arr[begin]));
        // 递归的出口
        if (ele == arr[mid]) {
            return mid;
        }
        // 比较 ele 和 arr[mid] 的值，缩小 ele 可能存在的区域
        if (ele < arr[mid]) {
            // 新的搜索区域为 [begin,mid-1]
            return interpolation_search(arr, begin, mid - 1, ele);
        } else {
            // 新的搜索区域为 [mid+1,end]
            return interpolation_search(arr, mid + 1, end, 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("查找失败");
        }
      
    }
}

如下是使用插值查找算法在 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} 序列中查找元素 2 的 Python 程序：

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