在JavaScript中实现块搜索

区块搜寻

就像二进制搜索一样，块搜索也是一种用于排序数组的搜索算法。基本思想是通过固定步长跳过或跳过某些元素代替搜索所有元素来检查更少的元素（与线性搜索相比）。

例如

假设我们有一个长度为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));

输出结果

以下是控制台上的输出-

10