C语言跳跃搜索算法详解（从零开始掌握高效查找技巧）

例如，在一个包含 16 个元素的数组中，最优步长通常是 √16 = 4。我们先检查索引 0、4、8、12……直到找到一个大于目标值的元素，然后回退一步，在该区间内进行线性搜索。

为什么使用跳跃搜索？

• 比线性搜索快（时间复杂度 O(√n)）
• 不需要像二分查找那样频繁地访问中间元素（对某些存储结构更友好）
• 实现简单，逻辑清晰

C语言实现跳跃搜索

下面是一个完整的 C语言实现跳跃搜索 的代码示例：

#include <stdio.h>#include <math.h>// 跳跃搜索函数int jumpSearch(int arr[], int n, int x) {    // 计算最优步长    int step = (int)sqrt(n);    int prev = 0;    // 跳跃阶段：找到目标可能所在的块    while (arr[(step < n ? step : n) - 1] < x) {        prev = step;        step += (int)sqrt(n);        if (prev >= n) {            return -1; // 未找到        }    }    // 线性搜索阶段：在 [prev, min(step, n)] 区间内查找    for (int i = prev; i < (step < n ? step : n); i++) {        if (arr[i] == x) {            return i; // 返回索引        }    }    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 x = 55;    int result = jumpSearch(arr, n, x);    if (result != -1) {        printf("元素 %d 在索引 %d 处找到。\n", x, result);    } else {        printf("元素 %d 未找到。\n", x);    }    return 0;}  

代码解析

1. step = sqrt(n)：设定跳跃步长为数组长度的平方根，这是理论上的最优值。
2. 第一个 while 循环：不断跳跃，直到找到一个大于目标值的块。
3. 第二个 for 循环：在确定的块内进行线性搜索。
4. 如果找到目标，返回其索引；否则返回 -1。

时间与空间复杂度

• 时间复杂度：O(√n) —— 这是跳跃搜索的核心优势。
• 空间复杂度：O(1) —— 只使用了常量级额外空间。

适用场景

高效查找算法如跳跃搜索特别适用于以下情况：

• 数组已排序
• 数据存储在链表等不支持随机访问的结构中（虽然本例用数组，但思想可迁移）
• 希望避免二分查找中频繁的中间索引计算

小结

通过本教程，你已经掌握了 C语言跳跃搜索算法 的原理、实现和应用场景。它是一种简单而高效的 跳跃查找 方法，尤其适合初学者理解分块搜索的思想。虽然在实际项目中二分查找更常用，但跳跃搜索为你打开了一扇理解算法设计的大门。

现在，动手试试修改上面的代码，用不同的数组和目标值测试吧！实践是掌握 C语言实现跳跃搜索 和其他 高效查找算法 的最佳方式。