JavaScriptでのブロック検索の実装

ブロック検索

バイナリ検索と同様に、ブロック検索もソートされた配列の検索アルゴリズムです。基本的な考え方は、すべての要素を検索する代わりに、固定の手順で先に進むか、一部の要素をスキップすることで、（線形検索よりも）少ない要素をチェックすることです。

例

長さnの配列arrとサイズmのブロック（ジャンプされる）があるとします。次に、インデックスarr [0]、arr [m]、arr [2 * m]、...、arr [k*m]などを検索します。

区間arr[k* m]

このアルゴリズムの時間計算量は-

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