跳跃搜索

跳跃搜索（Jump Search）是一种用于有序数组的搜索算法，它通过固定步长跳跃式地检查元素，最终在确定的目标范围内执行线性搜索。该算法的时间复杂度为$O(\sqrt{n})$，比线性搜索（$O(n)$）更快，但比二分搜索（$O(\log n)$）稍慢，适用于中等规模的数据集或无法直接访问内存的情况（如链表）。

算法原理

跳跃搜索的核心思想是通过跳跃式前进缩小搜索范围，再在局部执行精确匹配。步骤如下：

1. 确定跳跃步长：通常选择步长$m=\lfloor \sqrt{n}\rfloor$，其中$n$是数组长度。 2. 跳跃阶段：从索引0开始，每次跳跃$m$步，比较当前元素与目标值：

  - 若当前元素等于目标值，直接返回索引。
  - 若当前元素小于目标值，继续跳跃。
  - 若当前元素大于目标值，停止跳跃。

3. 线性搜索阶段：在上一个跳跃点和当前跳跃点之间执行线性搜索。

graph TD A[开始] --> B[初始化步长m=√n] B --> C[从索引0跳跃m步] C --> D{当前元素 vs 目标值} D -- 等于 --> E[返回索引] D -- 小于 --> F[继续跳跃] D -- 大于 --> G[回退到上一个跳跃点] G --> H[线性搜索] H --> I[找到目标或结束]

代码实现

以下是Python实现的跳跃搜索算法：

import math

def jump_search(arr, target):
    n = len(arr)
    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

    # 线性搜索阶段
    while arr[prev] < target:
        prev += 1
        if prev == min(step, n):
            return -1

    if arr[prev] == target:
        return prev
    return -1

# 示例
arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]
target = 34
print(f"目标 {target} 的索引是: {jump_search(arr, target)}")

输出：

目标 34 的索引是: 9

复杂度分析

• 时间复杂度：$O(\sqrt{n})$，由跳跃阶段（$n/m$次比较）和线性阶段（最多$m-1$次比较）组成。
• 空间复杂度：$O(1)$，仅需常数空间。

实际应用

1. 内存受限环境：跳跃搜索比二分搜索更适合链表等非连续存储结构，因为二分搜索需要频繁随机访问。 2. 动态数据集：当数据频繁插入且保持有序时，跳跃搜索的适应性优于二分搜索。

与二分搜索对比

跳跃搜索 vs 二分搜索

特性	跳跃搜索	二分搜索
时间复杂度	$O(\sqrt{n})$	$O(\log n)$
空间复杂度	$O(1)$	$O(1)$
数据要求	有序数组/链表	有序数组
适用场景	中等规模数据或链表	大规模随机访问数据

变体与优化

• 自适应步长：根据数据分布动态调整步长（如指数跳跃）。
• 混合策略：结合二分搜索快速定位范围。