在 JavaScript 中实现块搜索

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/2/21 11:24:17

块搜索

与二分搜索一样，块搜索也是一种用于排序数组的搜索算法。其基本思想是通过按固定步骤向前跳跃或跳过一些元素来代替搜索所有元素，以检查更少的元素(比线性搜索少)。

例如

假设我们有一个长度为 n 的数组 arr 和一个大小为 m 的块(要跳跃)。然后我们在索引 arr[0]、arr[m]、arr[2 * m]、...、arr[k * m] 等处进行搜索。

一旦我们找到区间 arr[k * m] < x < arr[(k+1) * m]，我们就从索引 k * m 执行线性搜索操作来找到元素 x。

该算法的时间复杂度为 −

O(√n)

示例

以下是代码 −

const arr = [1, 4, 6, 7, 9, 12, 15, 16, 17, 23, 25, 26, 27, 31];
const target = 25;
const blockSearch = (arr = [], target) => {
   let { length: len } = arr;
   let step = Math.floor(Math.sqrt(len));
   let blockStart = 0
   let currentStep = step;
   while (arr[Math.min(currentStep, len) - 1] < target) {
      blockStart = currentStep;
      currentStep += step;
      if (blockStart >= len)
         return -1;
   }
   while (arr[blockStart] < target){
      blockStart++;
      if (blockStart == Math.min(currentStep, len))
         return -1;
   }
   if (arr[blockStart] == target)
      return blockStart
   else
      return -1;
};
console.log(blockSearch(arr, target));