编程导航会员会员
登录/注册

一文带你学会"跳跃查找"

大家好，我是算法学长，一个热爱分享算法知识的开发者。 算法 0 基础、校招冲刺中大厂，推荐使用算法导航：https://algo.codefather.cn/ 交互式算法学习平台，带大家系统化学习算法。

跳跃查找

介绍

跳跃查找（Jump Search）是一种在有序数组中查找元素的算法，核心思想是通过跳过固定步长的元素来缩小搜索范围，然后在缩小的区间内进行线性查找。跳跃查找是二分查找和线性查找的混合体，特别适合大型有序数据集。

跳跃查找的效率取决于步长的选择。在最佳情况下，跳跃查找的时间复杂度可以达到 O(√n)，优于线性查找的 O(n)，但不如二分查找的 O(log n)。但是在一些具体场景下，跳跃查找比二分查找表现更好，比如当内存中访问顺序元素比随机访问更高效的时候。

算法步骤

  1. 确定跳跃步长（通常取 √n，n 是数组长度）
  2. 从数组开头开始，每次跳过步长个元素，直到找到大于或等于目标值的元素或达到数组末尾
  3. 如果找到的元素大于目标值，则回退一步，在该区间内进行线性查找
  4. 如果找到目标值，返回其索引；否则返回未找到标识

核心特性

  • 分块查找：将数组分成大小为 √n 的块，跳跃式地查找
  • 步长选择：最优步长为 √n，在时间和空间复杂度间取得平衡
  • 时间复杂度：平均情况为 O(√n)
  • 空间复杂度：O(1)，不需要额外空间
  • 适用条件：必须在有序数组上进行操作

基础实现

接下来大家一起看下跳跃查找的部分主流语言实现：

Java实现

▼
java
复制代码
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;  // 未找到元素
            }
        }
        
        // 线性查找阶段
        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 = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
        int target = 55;
        
        int index = jumpSearch(arr, target);
        
        if (index != -1) {
            System.out.println("元素 " + target + " 在索引 " + index + " 处找到");
        } else {
            System.out.println("元素 " + target + " 未在数组中找到");
        }
    }
}

注意，在上述代码里，通过：

▼
java
复制代码
// 确定最佳步长
int step = (int) Math.floor(Math.sqrt(n));

确定了跳跃查找最关键的步长参数，这里会直接影响算法的效率。

JavaScript 实现

▼
javascript
复制代码
function jumpSearch(arr, target) {
    const n = arr.length;
    
    // 确定最佳步长
    const step = Math.floor(Math.sqrt(n));
    
    // 跳跃查找阶段
    let prev = 0;
    while (arr[Math.min(step, n) - 1] < target) {
        prev = step;
        step += Math.floor(Math.sqrt(n));
        if (prev >= n) {
            return -1;  // 未找到元素
        }
    }
    
    // 线性查找阶段
    while (arr[prev] < target) {
        prev++;
        
        // 如果已到达下一步长或数组末尾，则未找到元素
        if (prev == Math.min(step, n)) {
            return -1;
        }
    }
    
    // 检查是否找到目标元素
    if (arr[prev] == target) {
        return prev;  // 返回元素索引
    }
    
    return -1;  // 未找到元素
}

// 测试
const arr = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610];
const target = 55;

const index = jumpSearch(arr, target);

if (index !== -1) {
    console.log(`元素 ${target} 在索引 ${index} 处找到`);
} else {
    console.log(`元素 ${target} 未在数组中找到`);
}

Python 实现

▼
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, 233, 377, 610]
target = 55

index = jump_search(arr, target)

if index != -1:
    print(f"元素 {target} 在索引 {index} 处找到")
else:
    print(f"元素 {target} 未在数组中找到")

Go 实现

▼
go
复制代码
package main

import (
    "fmt"
    "math"
)

func jumpSearch(arr []int, target int) int {
    n := len(arr)
    
    // 确定最佳步长
    step := int(math.Sqrt(float64(n)))
    
    // 跳跃查找阶段
    prev := 0
    for arr[min(step, n)-1] < target {
        prev = step
        step += int(math.Sqrt(float64(n)))
        if prev >= n {
            return -1  // 未找到元素
        }
    }
    
    // 线性查找阶段
    for arr[prev] < target {
        prev++
        
        // 如果已到达下一步长或数组末尾，则未找到元素
        if prev == min(step, n) {
            return -1
        }
    }
    
    // 检查是否找到目标元素
    if arr[prev] == target {
        return prev  // 返回元素索引
    }
    
    return -1  // 未找到元素
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func main() {
    arr := []int{0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}
    target := 55
    
    index := jumpSearch(arr, target)
    
    if index != -1 {
        fmt.Printf("元素 %d 在索引 %d 处找到\n", target, index)
    } else {
        fmt.Printf("元素 %d 未在数组中找到\n", target)
    }
}

C 实现

▼
c
复制代码
#include <stdio.h>
#include <math.h>

int min(int a, int b) {
    return (a < b) ? a : b;
}

int jumpSearch(int arr[], int n, int target) {
    // 确定最佳步长
    int step = (int)sqrt(n);
    
    // 跳跃查找阶段
    int prev = 0;
    while (arr[min(step, n) - 1] < target) {
        prev = step;
        step += (int)sqrt(n);
        if (prev >= n) {
            return -1;  // 未找到元素
        }
    }
    
    // 线性查找阶段
    while (arr[prev] < target) {
        prev++;
        
        // 如果已到达下一步长或数组末尾，则未找到元素
        if (prev == min(step, n)) {
            return -1;
        }
    }
    
    // 检查是否找到目标元素
    if (arr[prev] == target) {
        return prev;  // 返回元素索引
    }
    
    return -1;  // 未找到元素
}

int main() {
    int arr[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 55;
    
    int index = jumpSearch(arr, n, target);
    
    if (index != -1) {
        printf("元素 %d 在索引 %d 处找到\n", target, index);
    } else {
        printf("元素 %d 未在数组中找到\n", target);
    }
    
    return 0;
}

C++ 实现

▼
cpp
复制代码
#include <iostream>
#include <cmath>
#include <algorithm>

int jumpSearch(int arr[], int n, int target) {
    // 确定最佳步长
    int step = std::floor(std::sqrt(n));
    
    // 跳跃查找阶段
    int prev = 0;
    while (arr[std::min(step, n) - 1] < target) {
        prev = step;
        step += std::floor(std::sqrt(n));
        if (prev >= n) {
            return -1;  // 未找到元素
        }
    }
    
    // 线性查找阶段
    while (arr[prev] < target) {
        prev++;
        
        // 如果已到达下一步长或数组末尾，则未找到元素
        if (prev == std::min(step, n)) {
            return -1;
        }
    }
    
    // 检查是否找到目标元素
    if (arr[prev] == target) {
        return prev;  // 返回元素索引
    }
    
    return -1;  // 未找到元素
}

int main() {
    int arr[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610};
    int n = sizeof(arr) / sizeof(arr[0]);
    int target = 55;
    
    int index = jumpSearch(arr, n, target);
    
    if (index != -1) {
        std::cout << "元素 " << target << " 在索引 " << index << " 处找到" << std::endl;
    } else {
        std::cout << "元素 " << target << " 未在数组中找到" << std::endl;
    }
    
    return 0;
}

优化策略

自适应步长

根据数据规模动态调整步长：

▼
java
复制代码
public static int optimizedJumpSearch(int[] arr, int target) {
    int n = arr.length;
    
    // 根据数组大小调整步长
    int step;
    if (n <= 100) {
        step = 5;  // 小数组使用较小步长
    } else if (n <= 10000) {
        step = (int) Math.floor(Math.sqrt(n));  // 中等数组使用标准步长
    } else {
        step = (int) Math.floor(Math.cbrt(n) * 3);  // 大数组使用更大步长
    }
    
    // 后续跳跃查找逻辑
    // ...
}

缓存友好优化

根据计算机缓存特性优化：

▼
java
复制代码
public static int cacheOptimizedJumpSearch(int[] arr, int target) {
    int n = arr.length;
    
    // 根据缓存行大小选择步长
    // 假设每个缓存行为64字节，每个int为4字节，则一个缓存行可以存储16个int
    int cacheLineSize = 16;
    int step = (int) Math.floor(Math.sqrt(n / cacheLineSize)) * cacheLineSize;
    
    if (step < cacheLineSize) {
        step = cacheLineSize;
    }
    
    // 后续跳跃查找逻辑
    // ...
}

优缺点

优点

  • 比线性查找更高效，时间复杂度为 O(√n)
  • 比二分查找更易于实现
  • 在链表等只能顺序访问的数据结构上有优势
  • 良好的内存局部性，更利于缓存命中

缺点

  • 时间复杂度不如二分查找的 O(log n)
  • 性能对步长的选择比较敏感
  • 必须是有序数组
  • 对于小数组，优势不明显
  • 针对频繁动态变化的数据结构，需要重新计算最优步长

应用场景

1）处理大型有序数组，尤其是当内存访问成本高时

2）在内存局部性要求高的系统中，如嵌入式系统或低级系统优化

3）随机访问成本高于顺序访问时作为二分查找的替代方案

4）在链表等顺序访问数据结构上查找

5）外部存储设备上的数据查找，比如磁盘存储，顺序读取比随机读取更高效

扩展

跳跃链表实现

将跳跃查找的思想应用到链表数据结构：

▼
java
复制代码
class Node {
    int data;
    Node next;
    
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public static int jumpSearchInLinkedList(Node head, int target) {
    if (head == null) {
        return -1;
    }
    
    // 计算链表长度
    int length = 0;
    Node temp = head;
    while (temp != null) {
        length++;
        temp = temp.next;
    }
    
    // 确定步长
    int step = (int) Math.floor(Math.sqrt(length));
    
    // 跳跃查找阶段
    Node current = head;
    Node prev = null;
    int position = 0;
    
    while (current != null && current.data < target) {
        // 记住上一个跳跃点
        prev = current;
        
        // 跳跃到下一个位置
        for (int i = 0; i < step && current != null; i++) {
            current = current.next;
            position++;
        }
    }
    
    // 回退到上一个跳跃点
    if (current == null || (current != head && current.data > target)) {
        current = prev;
        position -= step;
    }
    
    // 线性查找阶段
    while (current != null && current.data < target) {
        current = current.next;
        position++;
    }
    
    // 检查是否找到目标元素
    if (current != null && current.data == target) {
        return position;
    }
    
    return -1;  // 未找到元素
}

跳跃查找与其他算法组合

在大型数据结构中结合多种查找算法：

▼
java
复制代码
public static int hybridSearch(int[] arr, int target) {
    int n = arr.length;
    
    // 根据数组大小选择算法
    if (n <= 20) {
        // 小数组使用线性查找
        return linearSearch(arr, target);
    } else if (n <= 1000) {
        // 中等数组使用跳跃查找
        return jumpSearch(arr, target);
    } else {
        // 大数组使用二分查找
        return binarySearch(arr, target);
    }
}

private static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

private static int binarySearch(int[] arr, int target) {
    int left = 0;
    int right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

测验

这里准备了一些测试题，方便大家判断自己的掌握情况：

  1. 跳跃查找的最优步长是多少？为什么这个步长是最优的？
  2. 跳跃查找的时间复杂度是多少？与线性查找和二分查找相比如何？
  3. 在什么情况下，跳跃查找比二分查找更有优势？

测验答案

  1. 跳跃查找的最优步长是 √n，其中 n 是数组长度。这个步长在时间复杂度方面达到了最优平衡，让算法的时间复杂度达到 O(√n)。
  2. O(√n)，优于线性查找的 O(n)，但不如二分查找的 O(log n)。
  3. 顺序访问比随机访问更高效的时候，跳跃查找比二分查找更好用，比如在链表、磁盘存储或缓存友好型系统中。

相关的 LeetCode 热门题目

给大家推荐一些可以用来练手的相关题目：

学算法就上算法导航：https://algo.codefather.cn/ ，交互式算法学习平台！

算法
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
算法学长
算法学长
等级vip
内容推荐
更多
最近刷算法的一些心得~
6
Claude Code 源码架构深度解析：1884 个文件背后的 AI 编程工具设计哲学
23
深度解析 Claude Code 记忆系统：从源码看 AI 编程助手如何"记住"你的项目
6
LeetCode Hot 100 二分查找篇 - 每次砍一半，六道题从入门到穿透
2
卷AI、卷算法、2026 年的前端工程师到底在卷什么？
7
作者分享
更多
一文带你学会"最近点对问题"
4
一文带你学会"分治算法"
4
一文带你学会"KMP 算法"
6
一文带你学会"Boyer-Moore算法"
3
一文带你学会"Rabin-Karp算法"
3
下载 APP