编辑“︁跳跃搜索”︁

{{DISPLAYTITLE:跳跃搜索}}

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

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

1. '''确定跳跃步长'''：通常选择步长<math>m = \lfloor \sqrt{n} \rfloor</math>，其中<math>n</math>是数组长度。
2. '''跳跃阶段'''：从索引0开始，每次跳跃<math>m</math>步，比较当前元素与目标值：
   - 若当前元素等于目标值，直接返回索引。
   - 若当前元素小于目标值，继续跳跃。
   - 若当前元素大于目标值，停止跳跃。
3. '''线性搜索阶段'''：在上一个跳跃点和当前跳跃点之间执行线性搜索。

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

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

<syntaxhighlight lang="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)}")
</syntaxhighlight>

'''输出'''：
<pre>
目标 34 的索引是: 9
</pre>

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

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

== 与二分搜索对比 ==
{| class="wikitable"
|+ 跳跃搜索 vs 二分搜索
! 特性 !! 跳跃搜索 !! 二分搜索
|-
| 时间复杂度 || <math>O(\sqrt{n})</math> || <math>O(\log n)</math>
|-
| 空间复杂度 || <math>O(1)</math> || <math>O(1)</math>
|-
| 数据要求 || 有序数组/链表 || 有序数组
|-
| 适用场景 || 中等规模数据或链表 || 大规模随机访问数据
|}

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

{{算法导航|搜索算法}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:搜索算法]]