第 25 课 - 跳跃搜索

所属模块： 搜索算法
难度： intermediate
标签： jump-search, block, sqrt
上一课： 插值搜索
下一课： 指数搜索

1. 学习目标

通过本课学习，你将能够：

理解跳跃搜索（Jump Search）的基本思想和工作原理。
分析跳跃搜索的时间复杂度，并理解其适用场景。
实现一个跳跃搜索算法。
对比跳跃搜索与线性搜索、二分搜索的优缺点。
选择合适的跳跃步长以优化算法性能。

2. 核心概念

想象一下，你在一个排列得整整齐齐的书架前找一本特定的书。线性搜索就像你从第一本书开始，一本一本往后翻，直到找到为止，效率很低。二分搜索则聪明得多，你每次都从中间开始，能快速缩小范围，但有时“猜”得不太准（比如书名首字母分布不均匀时）。

跳跃搜索（Jump Search）提供了一种折中方案。它像一个经验丰富的图书管理员：

固定步长跳跃：你不会一本本翻，而是决定一个跳跃的步长，比如每跳过 m 本书就停下来看看。
找到目标区间：当你停下的那本书的书名首字母大于要找的书时，你就知道目标书一定在你上一次停下和当前位置之间的这个“块”里。
线性搜索：然后在这个相对较小的块里，再进行细致的线性搜索。

这个“块”的大小就是我们的跳跃步长 m。那么，m 选多大最合适呢？一个经典的选择是 m = √n（数组长度的平方根）。为什么？因为这样能让跳跃次数和块内搜索次数的总和最小，实现最优的平衡。

关键点：跳跃搜索要求待搜索的数组必须是有序的。

时间复杂度分析：

最优步长 m = √n 时，我们需要跳跃 √n 次（跳过 √n 个块），在最后一个块内最多进行 √n - 1 次比较。
总的时间复杂度是 O(√n)。它介于 O(n)（线性搜索）和 O(log n)（二分搜索）之间。

3. 代码示例

下面是一个完整的、可运行的 Python 实现，包含了详细的注释。

import math

def jump_search(arr, target):
    """
    使用跳跃搜索算法在有序数组中查找目标值。

    参数:
    arr (list): 一个已排序的列表。
    target (any): 要搜索的目标值。

    返回:
    int: 目标值在数组中的索引，如果未找到则返回 -1。
    """
    n = len(arr)
    if n == 0:
        return -1

    # 1. 确定最优的跳跃步长 (square root of n)
    step = int(math.sqrt(n))

    # 2. 初始化跳跃指针
    prev = 0  # 当前块的起始位置
    curr = step  # 当前跳跃到的位置 (下一个块的起始位置)

    # 3. 跳跃阶段：找到第一个 arr[curr] >= target 的块
    # 循环条件：curr < n 且当前块的最大值小于目标值
    while curr < n and arr[curr] < target:
        prev = curr
        curr += step
        # 防止 curr 超出数组范围
        if curr > n:
            curr = n  # 将 curr 设置为 n，表示最后一个块

    # 4. 线性搜索阶段：在从 prev 到 min(curr, n) 的块中进行线性搜索
    # 注意：这里的循环上限是 min(curr, n)，因为 curr 可能被设置为 n (超出数组索引)
    for i in range(prev, min(curr, n)):
        if arr[i] == target:
            return i  # 找到目标，返回索引

    # 5. 如果循环结束仍未找到
    return -1

# 测试代码
if __name__ == "__main__":
    # 创建一个已排序的测试数组
    test_array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    target_value = 7

    print(f"在数组 {test_array} 中搜索目标值 {target_value}...")
    result_index = jump_search(test_array, target_value)

    if result_index != -1:
        print(f"成功！目标值 {target_value} 的索引为: {result_index}")
    else:
        print(f"失败。目标值 {target_value} 不在数组中。")

    # 测试一个不存在的目标值
    target_not_found = 10
    print(f"\n在数组 {test_array} 中搜索目标值 {target_not_found}...")
    result_index_2 = jump_search(test_array, target_not_found)
    if result_index_2 != -1:
        print(f"成功！目标值 {target_not_found} 的索引为: {result_index_2}")
    else:
        print(f"失败。目标值 {target_not_found} 不在数组中。")

运行结果：

在数组 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 中搜索目标值 7...
成功！目标值 7 的索引为: 7

在数组 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 中搜索目标值 10...
失败。目标值 10 不在数组中。

4. 实践练习

练习 1：基础实现 使用你熟悉的语言，根据上述算法描述，实现一个 jump_search 函数。使用测试数组 [10, 20, 30, 40, 50, 60, 70, 80, 90] 和目标值 60 进行测试，预期输出索引 5。

练习 2：错误处理与边界情况 修改你的函数，使其能够优雅地处理以下情况：

输入数组为空。
目标值小于数组第一个元素。
目标值大于数组最后一个元素。请在主程序中添加针对这些情况的测试用例。

练习 3：步长探索 尝试修改 step 的值，分别使用 step = 1（退化为线性搜索）、step = n（几乎每次只检查一个元素，效率极低）和 step = 2，在同一个较大数组（例如 1000 个元素）上运行并计时。观察并记录不同步长对性能的影响。

5. 常见错误

步长选择错误：
- 错误：将步长 step 设置为 1，这时算法退化成了线性搜索，失去了跳跃的意义。
- 正确：使用 int(math.sqrt(n)) 作为默认步长。
边界条件处理不当：
- 错误：在循环 while curr < n and arr[curr] < target 中，当 curr 超过数组长度 n 时，arr[curr] 会引发 IndexError。
- 正确：在循环内更新 curr 后，必须检查 if curr > n 并将其设为 n。同样，在后续的线性搜索中，循环范围应是 (prev, min(curr, n))。
未处理空数组：
- 错误：直接对空列表 [] 调用 jump_search，在计算 math.sqrt(n) 时 n=0，这在某些语言中可能导致问题，或者在后续逻辑中出现错误。
- 正确：在函数开始处添加 if n == 0: return -1。
误解算法适用性：
- 错误：试图在无序数组上使用跳跃搜索。
- 正确：始终记住，跳跃搜索和其他二分变体一样，必须作用于有序数据。

6. 小结

核心思想：跳跃搜索通过以固定步长（通常为 √n）跳跃来快速定位目标可能所在的“块”，然后在该块内进行线性搜索。
时间复杂度：O(√n)。比线性搜索 O(n) 快，但比二分搜索 O(log n) 慢。
空间复杂度：O(1)，是原地算法。
适用场景：当访问顺序存储结构（如数组）的某个元素比进行比较操作成本更高时，跳跃搜索可能比二分搜索更优。因为二分搜索需要频繁跳转到数组中间，而跳跃搜索的跳转次数更少、更规律。
实现关键：
1. 正确计算并应用跳跃步长 step = √n。
2. 小心处理数组边界，防止越界访问。
3. 清晰划分“跳跃阶段”和“块内线性搜索阶段”。

掌握了跳跃搜索，你对搜索算法家族（线性、二分、插值、跳跃、指数）的理解又加深了一步。接下来，我们将学习另一种巧妙的搜索策略——指数搜索。

练习编辑器

rust