插值搜索

插值搜索（Interpolation Search）是一种改进的二分搜索算法，适用于均匀分布的有序数组。它通过计算目标值的预估位置来减少比较次数，平均时间复杂度为$O(\log \log n)$，但在最坏情况下（如非均匀分布数据）会退化为$O(n)$。

算法原理

插值搜索基于以下假设：如果数组元素均匀分布，则目标值的位置可通过线性插值公式估算： $pos=low+\lfloor \frac{(x-arr[low])\times (high-low)}{arr[high]-arr[low]}\rfloor$ 其中：

• arr 是已排序数组
• x 是目标值
• low 和 high 是当前搜索区间的边界

与二分搜索对比

插值搜索 vs 二分搜索

特性	插值搜索	二分搜索
时间复杂度（平均）	$O(\log \log n)$	$O(\log n)$
数据要求	必须均匀分布	任意有序数据
分区方式	动态计算位置	固定中点

算法步骤

1. 计算目标值的预估位置 pos 2. 若 arr[pos] == x，返回位置 3. 若 arr[pos] < x，在右子数组（pos+1 到 high）继续搜索 4. 若 arr[pos] > x，在左子数组（low 到 pos-1）继续搜索 5. 重复直到找到目标或区间无效

代码实现

以下是Python实现示例：

def interpolation_search(arr, x):
    low = 0
    high = len(arr) - 1
    
    while low <= high and arr[low] <= x <= arr[high]:
        # 计算插值位置
        pos = low + ((x - arr[low]) * (high - low)) // (arr[high] - arr[low])
        
        if arr[pos] == x:
            return pos
        elif arr[pos] < x:
            low = pos + 1
        else:
            high = pos - 1
    
    return -1  # 未找到

示例输入输出

输入：

arr = [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47]
x = 18

执行过程： 1. 初始 low=0, high=14 2. 计算 pos = 0 + ((18-10)*(14-0))//(47-10) ≈ 4 3. arr[4] = 18 匹配，返回索引4

输出：

Found at index 4

复杂度分析

• 最佳情况：$O(1)$（第一次命中）
• 平均情况：$O(\log \log n)$（均匀分布数据）
• 最坏情况：$O(n)$（如 [1,2,3,4,5,10000] 搜索5）

graph LR A[开始] --> B{计算pos} B -->|命中| C[返回索引] B -->|小于| D[搜索右子数组] B -->|大于| E[搜索左子数组] C --> F[结束] D --> B E --> B

应用场景

1. 电话簿搜索：人名按字母均匀分布时效率极高 2. 大规模科学数据：如温度传感器记录的均匀时间序列 3. 游戏高分榜：分数分布均匀的排名系统

注意事项

• 必须确保数组已排序且分布均匀，否则性能可能劣于二分搜索
• 对于小规模数据集（<100元素），线性搜索可能更简单高效
• 浮点数数组需处理除零错误（当arr[high]==arr[low]时）

扩展优化

可结合指数搜索（Exponential Search）先确定大致范围，再使用插值搜索精确定位，尤其适合未知大小的有序数据集。