带你读《图解算法小抄》十五、搜索（2）https://developer.aliyun.com/article/1348121?groupCode=tech_library
3.跳跃搜索
跳跃搜索（Jump Search）又称为块搜索（Block Search），是一种用于已排序数组的搜索算法。其基本思想是通过固定的步长跳跃或跳过一些元素，而不是搜索所有元素，从而检查较少的元素（相比于线性搜索）。
例如，假设我们有一个大小为 n 的数组 arr[]，以及一个块大小 m。我们在索引 arr[0]、arr[m]、arr[2 * m]、...、arr[k * m] 等处进行搜索。一旦我们找到区间 arr[k * m] < x < arr[(k+1) * m]，我们在索引 k * m 开始执行线性搜索操作，以找到元素 x。
什么是最优的块大小？ 在最坏的情况下，我们需要进行 n/m 次跳跃，如果最后一个检查的值大于要搜索的元素，则我们还需要进行 m - 1 次比较进行线性搜索。因此，在最坏情况下，总的比较次数为 ((n/m) + m - 1)。当 m = √n 时，函数 ((n/m) + m - 1) 的值最小。因此，最佳的步长大小是 m = √n。
1）复杂度
时间复杂度：O(√n) - 因为我们按块大小 √n 进行搜索。
2）完整实现
function jumpSearch(array, target) { const n = array.length; const blockSize = Math.floor(Math.sqrt(n)); let step = blockSize; let prev = 0; // 跳跃定位目标值的可能范围 while (array[Math.min(step, n) - 1] < target) { prev = step; step += blockSize; if (prev >= n) { return -1; // 目标值不在数组中 } } // 在目标值的可能范围内进行线性搜索 while (array[prev] < target) { prev++; if (prev === Math.min(step, n)) { return -1; // 目标值不在数组中 } } // 检查找到的元素是否是目标值 if (array[prev] === target) { return prev; // 找到目标值，返回索引 } return -1; // 未找到目标值}
3）参考资料
- GeeksForGeeks
- Wikipedia
带你读《图解算法小抄》十五、搜索（4）https://developer.aliyun.com/article/1348119?groupCode=tech_library
