跳跃查找
入门把"粗定位"和"细扫描"拆开，是分块搜索的直观入门版。
// 搜索输入
定义数组和目标值
可视化演示开发中
跳跃查找 的交互式动画即将上线，敬请期待。
1int jumpSearch(int arr[], int n, int target) {
2 int step = floor(sqrt(n));
3 int prev = 0;
4 while (prev < n && arr[min(step, n) - 1] < target) {
5 prev = step;
6 step += floor(sqrt(n));
7 if (prev >= n) return -1;
8 }
9 for (int i = prev; i < min(step, n); i++) {
10 if (arr[i] == target) return i;
11 }
12 return -1;
13}
复杂度分析
时间 O(√n)
空间 O(1)
最优 O(1)
最坏 O(√n)
算法讲解
跳跃查找把搜索过程拆成两段：先大步跳跃做粗定位，再回到候选块里逐个扫描。
页面里的 B 标记代表块尾检查点，你会先看到算法按固定步长查看这些块边界。
一旦某个块尾已经不小于目标值，就说明目标只可能出现在这个块内部，随后流程切换为线性扫描。
常用步长是 sqrt(n)，因为它能在"跳多少次"和"块内扫多长"之间取得相对均衡的折中。
这种思路很适合帮助理解分块索引、分页目录和两阶段检索等更大的系统设计。
时间复杂度约为 O(√n)，空间复杂度为 O(1)。