跳至主要內容

跳跃搜索

linwu大约 1 分钟

跳跃搜索

跳跃搜索(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

复杂度

时间复杂度O(√n) - 因为我们按块大小 √n 进行搜索。

完整实现

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; // 未找到目标值
}

参考资料

关注公众号

和小伙伴们一起学习

加入技术交流群

扫描二维码 备注加群