跳跃搜索算法详解（Python实现跳跃查找与分块搜索）

为什么使用跳跃搜索？

当你处理一个已排序的大数组，但又不希望像二分查找那样频繁地进行随机访问（例如在链表中），跳跃搜索是一个折中方案。它的时间复杂度为 O(√n)，优于线性搜索的 O(n)，虽然不如二分搜索的 O(log n)，但在某些 I/O 成本高的系统中表现更优。

Python 实现跳跃搜索算法

下面是一个完整的 Python 跳跃搜索 实现示例：

import mathdef jump_search(arr, target):    n = len(arr)    # 计算跳跃步长（通常取 √n）    step = int(math.sqrt(n))    prev = 0    # 跳跃阶段：找到目标值所在的块    while arr[min(step, n) - 1] < target:        prev = step        step += int(math.sqrt(n))        if prev >= n:            return -1  # 目标不在数组中    # 线性搜索阶段：在 [prev, min(step, n)] 区间内查找    for i in range(prev, min(step, n)):        if arr[i] == target:            return i  # 返回索引    return -1  # 未找到# 示例使用arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]target = 13result = jump_search(arr, target)if result != -1:    print(f"元素 {target} 在索引 {result} 处找到")else:    print(f"元素 {target} 未找到")

代码解析

• step = int(math.sqrt(n))：设定每次跳跃的步长为 √n，这是理论最优值。
• while 循环：不断跳跃，直到找到一个块，其最后一个元素 ≥ target。
• for 循环：在确定的块内执行线性搜索。
• 如果目标值不存在，函数返回 -1。

适用场景与局限性

✅ 适用场景：

• 数组已排序
• 需要减少比较次数，但又不能/不想使用二分查找
• 在顺序存储结构（如数组）中效果最佳

❌ 局限性：

• 仅适用于有序数组
• 性能不如二分查找（O(√n) vs O(log n)）
• 对小数组优势不明显

总结

跳跃搜索是一种简单而有效的分块搜索方法，特别适合初学者理解“分而治之”的思想。虽然在实际工程中二分查找更为常用，但掌握跳跃搜索有助于拓宽算法思维。无论你是学习Python跳跃搜索还是准备面试，这个算法都值得了解。

记住：跳跃搜索的核心是“先跳后查”，步长选 √n 最优！