第 24 课：插值搜索

学习目标

完成本课学习后，你将能够：

理解插值搜索的核心思想及其与二分查找的区别。
知道插值搜索的适用场景（数据均匀分布）及其在该场景下的性能优势。
掌握插值搜索算法的实现步骤及其时间复杂度分析。
通过编写代码，实现一个高效且能正确处理边界情况的插值搜索算法。

核心概念

想象一下，你正在一本按拼音排序的字典里查找“ 啊 ”这个字。你会直接翻到字典最前面，而不是先翻到中间。而如果要查“ 中 ”，你可能会翻到字典的中间位置。这就是插值搜索背后的基本思想。

与二分查找每次都将搜索区间一分为二不同，插值搜索会根据目标值在数组值范围内的分布，来估算它可能所在的位置。这就像在尺子上，根据两个端点刻度，找到中间某个值的位置。

它的估算公式为： position = low + ((target - arr[low]) * (high - low) / (arr[high] - arr[low]))

其中：

low 和 high 是当前搜索范围的起始和结束索引。
arr[low] 和 arr[high] 是对应索引处的值。
target 是我们要查找的目标值。

这个公式的本质是线性插值：它假设数据在 [arr[low], arr[high]] 之间是均匀分布的，然后根据 target 在这个值范围内的相对位置，来推测它在数组索引范围 [low, high] 中的相对位置。

关键前提：插值搜索的性能高度依赖于数据的分布。当数据均匀分布时，它通常比二分查找更快，时间复杂度可以达到 O(log log n)。但在最坏情况下（例如数据分布极不均匀），它的时间复杂度会退化到与顺序搜索相同的 O(n)。

代码示例

以下是一个完整的、带详细注释的 Python 实现：

def interpolation_search(arr, target):
    """
    对一个已排序的数组执行插值搜索。
    :param arr: 已排序的列表 (需要是数值类型)
    :param target: 要搜索的目标值
    :return: 目标值的索引，如果未找到则返回 -1
    """
    # 初始化左右指针
    low = 0
    high = len(arr) - 1

    # 循环条件：确保搜索范围有效，且目标值在可能范围内
    while low <= high and target >= arr[low] and target <= arr[high]:
        # 处理数组元素全部相同的情况，避免除以零错误
        if arr[low] == arr[high]:
            if arr[low] == target:
                return low
            else:
                break

        # 核心：使用插值公式估算位置
        pos = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))

        # 比较并调整搜索范围
        if arr[pos] == target:
            return pos  # 找到目标
        elif arr[pos] < target:
            low = pos + 1  # 目标在右半部分
        else:
            high = pos - 1  # 目标在左半部分

    return -1  # 未找到目标


# 测试示例
if __name__ == "__main__":
    # 测试用例1：均匀分布的数据
    uniform_data = [2, 5, 8, 12, 16, 23, 38, 42, 56, 72, 91]
    target1 = 23
    index1 = interpolation_search(uniform_data, target1)
    print(f"在均匀数据 {uniform_data} 中查找 {target1}: 索引为 {index1}")
    # 预期输出: 在均匀数据 [...] 中查找 23: 索引为 5

    # 测试用例2：非均匀分布的数据
    skewed_data = [1, 2, 3, 4, 5, 10, 20, 100, 200, 1000]
    target2 = 20
    index2 = interpolation_search(skewed_data, target2)
    print(f"在非均匀数据 {skewed_data} 中查找 {target2}: 索引为 {index2}")
    # 预期输出: 在非均匀数据 [...] 中查找 20: 索引为 6

    # 测试用例3：查找不存在的值
    target3 = 99
    index3 = interpolation_search(uniform_data, target3)
    print(f"在均匀数据 {uniform_data} 中查找 {target3}: 索引为 {index3}")
    # 预期输出: 在均匀数据 [...] 中查找 99: 索引为 -1

实践练习

基础实现：给定一个已按升序排列的整数列表 [10, 20, 30, 40, 50, 60, 70, 80, 90]，实现插值搜索函数，并查找数字 60。
- 要求：返回 60 所在的索引。
- 预期输出：5
边界与错误处理：修改你上面实现的函数，使其能正确处理以下情况：
- 输入列表为空。
- 输入列表中存在连续多个相同元素（例如 [3, 5, 5, 5, 9, 11]），并查找 5。
- 要求：确保在查找连续相同元素时不会陷入无限循环，并能返回第一个匹配项的索引。
- 预期输出：对于 [3, 5, 5, 5, 9, 11] 查找 5，应返回索引 1。
性能思考：编写一个小的基准测试，比较在以下两种数据上，插值搜索与二分查找（二分查找函数可自行实现或使用库）的性能差异：
- 数据集A：一个包含 100,000 个元素的均匀分布整数列表（例如 range(0, 1000000, 10)）。
- 数据集B：一个包含 100,000 个元素的指数分布（极不均匀）整数列表（例如元素值为 2**i， i 从0递增）。
- 要求：分别测量在两个数据集中查找一个中间值和一个末尾值所需的时间，并解释观察到的结果。

常见错误

忽视数据分布条件：这是最严重的错误。在非均匀分布的数据上使用插值搜索，其性能可能不升反降，甚至劣于二分查找。务必确保你的应用场景（如均匀分布的ID、分数等）适合此算法。
除以零错误：当 arr[high] == arr[low] 时，插值公式中的除数 (arr[high] - arr[low]) 为零。代码中必须先处理这种情况（如示例所示），否则程序会崩溃。
索引计算错误：插值公式的结果是浮点数，需要转换为整数索引（在Python中是 // 整除）。务必确保计算出的 pos 在 [low, high] 范围内，虽然理论上公式保证了这一点，但循环条件 target >= arr[low] and target <= arr[high] 提供了额外的安全保障。
循环终止条件不当：除了 low <= high，还必须加上 target >= arr[low] and target <= arr[high] 这个条件。这可以提前终止无意义的搜索（例如目标值比数组最小值还小），提高效率。

小结

核心思想：插值搜索是二分查找的“智能”版本，它通过值的分布来预测索引的位置，而不是盲目地每次取中点。
适用场景：数据均匀分布的已排序数组。例如，在大量均匀的ID号、温度读数或按字母顺序均匀分布的字符串列表中查找。
时间复杂度：
- 最佳/平均情况（均匀分布）： O(log log n) ，比二分查找的 O(log n) 更快。
- 最坏情况（极度不均匀分布）： O(n) ，退化为顺序查找。
与二分查找对比：插值搜索在理想情况下更快，但更“挑剔”数据，且公式稍复杂。二分查找更通用、稳定，在所有已排序数据上都保证 O(log n) 的性能。
实现关键：使用线性插值公式估算位置，并谨慎处理数据相同（除零）和边界条件。

在下一课中，我们将学习另一种适用于大型有序数组的搜索算法——跳跃搜索。

练习编辑器

rust