JavaScriptで二分探索（バイナリサーチ）を使ってクエリを検索する方法

問題の概要

ソート済みのリテラル配列を第1引数に、検索したいクエリ値を第2引数として受け取るJavaScript関数を作成する必要があります。この関数は二分探索（バイナリサーチ）アルゴリズムを使用して、クエリが配列内に存在するかどうかを判定します。

存在する場合はそのインデックスを返し、存在しない場合は -1 を返します。

二分探索アルゴリズムとは

二分探索は、ソート済みの配列にのみ適用できる高速な探索手法です。まず配列の中央要素を調べ、目的の値と比較します。

• 中央の値がクエリと一致すれば、そのインデックスを返す
• 中央の値がクエリより小さければ、配列の後半だけを対象に再び探索する
• 中央の値がクエリより大きければ、配列の前半だけを対象に再び探索する

探索範囲が毎回半分になるため、線形探索の O(n) に対して O(log n) という非常に効率的な計算量で実行できます。例えば100万件のデータでも、最大20回程度の比較で目的の値を見つけられることになります。

コード例

以下のコードは、再帰呼び出しを使って二分探索を実装したものです −

const arr = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23];
const binarySearch = (arr, query) => {
   let index = Math.floor(arr.length / 2);
   if (arr[index] === query){
      return index;
   }else if (arr.length === 1){
      return null;
   }else if (arr[index] < query) {
      arr = arr.slice(index + 1);
      let res = binarySearch(arr, query);
      if (res === null){
         return -1;
      }else {
         return index + 1 + res;
      };
   }else {
      let arr1 = arr.slice(0, index);
      return binarySearch(arr1, query);
   };
};
console.log(binarySearch(arr, 1));
console.log(binarySearch(arr, 7));
console.log(binarySearch(arr, 11));
console.log(binarySearch(arr, 12));
console.log(binarySearch(arr, 22));

コードのポイント

• Math.floor(arr.length / 2) で配列の中央インデックスを求めています。
• クエリが中央より大きい場合は slice(index + 1) で後半を切り出し、再帰の結果にオフセットを加算することで、元の配列上の正しい位置へ補正しています。
• クエリが中央より小さい場合は slice(0, index) で前半を切り出し、そのまま再帰呼び出しを行います。
• 要素が1つ残るまで探索しても一致しなかった場合には null を返し、最終的に -1 に変換して「見つからない」ことを示します。

出力

コンソールへの出力は次のようになります −

0
5
7
-1
13

それぞれの結果は以下を意味しています。

• 1 → インデックス 0 に存在
• 7 → インデックス 5 に存在
• 11 → インデックス 7 に存在
• 12 → 配列内に存在しないため -1
• 22 → インデックス 13 に存在

注意点：slice() のパフォーマンス

この実装では slice() によって毎回新しい配列を生成しているため、配列が大きくなるとメモリ消費やコピーのコストが無視できなくなります。実務では、開始位置と終了位置のインデックスを引数として渡し、部分配列を作らずに探索範囲を絞っていくインデックスベースの実装（反復処理または再帰）にすることで、より効率的に動作させることができます。