搜索算法系列之三(插值查找)

前言

插值查找仅适用于有序数据、有序数组，和二分查找类似，更讲究数据有序均匀分布。

算法原理

插值查找(interpolation search)是一种查找算法，它与二分查找类似，但在寻找元素时更加智能化。这种算法假设数据集是等距的或者有序的，然后根据要查找的值在数据集中的位置进行估计，而不是简单地将查找范围划分为两半。

插值查找的步骤如下：

确定查找范围：首先确定要查找的元素在哪个范围内。通常情况下，这是通过比较要查找的值和数据集的第一个和最后一个元素来确定的。
计算估计位置：通过插值公式计算要查找的值在当前查找范围内的估计位置。插值公式通常是 (value - array[low]) / (array[high] - array[low]) * (high - low) + low，其中 low 和 high 分别是当前查找范围的起始和结束位置。
检查估计位置：将估计位置与要查找的值进行比较。
- 如果估计位置上的值等于要查找的值，则找到了目标元素。
- 如果估计位置上的值大于要查找的值，则在估计位置的左侧继续进行插值查找。
- 如果估计位置上的值小于要查找的值，则在估计位置的右侧继续进行插值查找。
重复直到找到目标元素或者确定元素不存在。

插值查找适用于数据集分布比较均匀的情况下，因为它是根据数据集的分布情况进行估计的。在数据集分布不均匀的情况下，插值查找可能会失效，效率不如二分查找。

上述公式说明:

value为查找的值。low、high为数据集首尾下标。array[low]、array[high]为数据集首尾值。

(value-array[low])/(array[high]-array[low])计算查找值在有序队列所处位置的比值。

代码实现(c)

#include <stdio.h>
 
// 插值查找函数
int interpolationSearch(int arr[], int low, int high, int key) {
    if (low <= high) {
        // 计算插值的索引
        int mid = low + (high - low) * (double)((key - arr[low]) / (arr[high] - arr[low]));
 
        // 如果元素等于key，返回mid
        if (arr[mid] == key)
            return mid;
 
        // 如果元素小于key，在右侧递归查找
        if (arr[mid] > key)
            return interpolationSearch(arr, low, mid - 1, key);
 
        // 如果元素大于key，在左侧递归查找
        return interpolationSearch(arr, mid + 1, high, key);
    }
 
    // 如果数组不存在key，返回-1
    return -1;
}
 
int main() {
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key = 7;
 
    // 查找元素
    int index = interpolationSearch(arr, 0, n - 1, key);
 
    // 输出结果
    if (index != -1)
        printf("元素在数组中的索引为: %d\n", index);
    else
        printf("元素不在数组中。\n");
 
    return 0;
}

注意计算比例时转double类型，否则会失效。