C++跳跃搜索算法详解（小白也能学会的分块查找技术）

跳跃搜索的时间复杂度

- 最佳步长通常取 √n（n 为数组长度）
- 时间复杂度：O(√n)
- 空间复杂度：O(1)

C++跳跃搜索算法实现

下面是一个完整的 C++ 实现，包含详细注释：

#include <iostream>#include <vector>#include <cmath>// 跳跃搜索函数int jumpSearch(const std::vector<int>& arr, int target) {    int n = arr.size();    if (n == 0) return -1; // 空数组处理    // 计算最佳步长：√n    int step = static_cast<int>(std::sqrt(n));    int prev = 0;    // 跳跃阶段：找到目标可能所在的块    while (arr[std::min(step, n) - 1] < target) {        prev = step;        step += static_cast<int>(std::sqrt(n));        if (prev >= n) return -1; // 超出范围，未找到    }    // 线性搜索阶段：在 [prev, min(step, n)) 区间内查找    for (int i = prev; i < std::min(step, n); ++i) {        if (arr[i] == target) {            return i; // 返回索引        }    }    return -1; // 未找到}int main() {    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21};    int target = 13;    int result = jumpSearch(arr, target);    if (result != -1) {        std::cout << "元素 " << target << " 在索引 " << result << " 处找到。\n";    } else {        std::cout << "元素 " << target << " 未找到。\n";    }    return 0;}

代码解析

• step = √n：这是理论最优步长，能最小化总比较次数。
• 跳跃阶段：不断以 step 为单位向前跳，直到 arr[step-1] ≥ target。
• 线性搜索阶段：在上一个块（prev 到 step-1）中逐个查找。
• 注意使用 std::min(step, n) 防止数组越界。

适用场景与优缺点

优点：

• 比线性搜索快（O(√n) vs O(n)）
• 只需向前跳，回退次数少（适合链表等结构）

缺点：

• 必须用于有序数组
• 性能不如二分查找（O(log n)）

总结

通过本教程，你已经掌握了C++跳跃搜索算法的核心思想与实现方法。虽然它不是最快的查找算法，但在特定场景下（如回退成本高）仍有其价值。建议你动手运行上面的代码，修改数组和目标值，加深理解。

记住，学习分块搜索C++不仅能提升你的算法能力，还能帮助你在面试中脱颖而出。继续练习更多C++查找算法，如二分查找、插值查找等，构建完整的算法知识体系！

关键词回顾：C++跳跃搜索算法、跳跃搜索实现、C++查找算法、分块搜索C++