Java跳跃搜索详解（快速掌握跳跃搜索算法在Java中的实现）

例如，对于一个长度为 16 的数组，最优跳跃步长为 √16 = 4。算法会先检查索引 0、4、8、12……直到找到一个大于目标值的元素，然后回退到上一个块，在该块内线性查找。

跳跃搜索 vs 其他查找算法

• 线性搜索：时间复杂度 O(n)，适用于无序数组。
• 二分搜索：时间复杂度 O(log n)，但需要随机访问（如数组），且实现略复杂。
• 跳跃搜索：时间复杂度 O(√n)，仅需向前遍历，适合某些只能单向遍历的数据结构。

Java 实现跳跃搜索

下面是一个完整的 Java 跳跃搜索实现：

import java.util.Arrays;public class JumpSearch {    public static int jumpSearch(int[] arr, int target) {        int n = arr.length;        int step = (int) Math.floor(Math.sqrt(n)); // 跳跃步长        int prev = 0;        // 跳跃阶段：找到目标值所在的块        while (arr[Math.min(step, n) - 1] < target) {            prev = step;            step += (int) Math.floor(Math.sqrt(n));            if (prev >= n) {                return -1; // 未找到            }        }        // 线性搜索阶段：在 [prev, step) 区间内查找        while (arr[prev] < target) {            prev++;            if (prev == Math.min(step, n)) {                return -1; // 未找到            }        }        // 检查是否找到目标        if (arr[prev] == target) {            return prev; // 返回索引        }        return -1; // 未找到    }    public static void main(String[] args) {        int[] arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21};        int target = 13;        int result = jumpSearch(arr, target);        if (result != -1) {            System.out.println("元素 " + target + " 在索引 " + result + " 处找到。");        } else {            System.out.println("元素 " + target + " 未找到。");        }    }}

代码解析

1. step 初始化为 √n，这是理论上的最优跳跃步长。
2. 第一个 while 循环用于跳跃，直到找到一个元素 ≥ target。
3. 第二个 while 循环在线性范围内查找目标值。
4. 如果找到，返回索引；否则返回 -1。

时间与空间复杂度

• 时间复杂度：O(√n)
• 空间复杂度：O(1)

适用场景

跳跃搜索特别适合以下情况：

• 数据已排序（必须！）
• 不支持随机访问，但支持单向遍历（如链表，虽然实现较复杂）
• 希望比线性搜索更快，又不想使用递归或复杂逻辑

总结

通过本教程，你已经掌握了 Java跳跃搜索 的核心原理和实现方法。作为一种介于线性搜索和二分搜索之间的算法，跳跃搜索算法 在特定场景下非常实用。记住，它只适用于有序数组，并且其性能优势在大型数据集中更为明显。

如果你正在学习 Java查找算法 或准备面试，不妨动手实现一下这个 分块搜索Java 的经典案例！