JavaScriptでブロック検索を実装する方法【O(√n)の探索アルゴリズム】

ブロック検索とは

ブロック検索（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を特定します。

このアルゴリズムの時間計算量は以下の通りです。

O(√n)

実装例

以下がJavaScriptによる実装コードです。

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));

コードの解説

まず、Math.floor(Math.sqrt(len))によってブロックサイズ（ジャンプ幅）を算出します。最初のwhileループでは、現在位置の値がターゲットより小さい間、ブロック単位でスキップを繰り返し、目的の要素が含まれるブロック範囲を特定します。続くwhileループでは、そのブロック内の先頭から1つずつ値を比較する線形検索を行います。最後に、一致する要素が見つかればそのインデックスを返し、見つからなければ-1を返します。

出力結果

コンソールには以下のように表示されます。

10