JavaScriptで二分探索（バイナリサーチ）を実装する方法

二分探索（バイナリサーチ）は、ソート済みの配列から特定の値を効率的に検索するためのアルゴリズムです。探索範囲を半分ずつ絞り込みながら処理を進めるため、先頭から順に調べる線形探索と比べてはるかに高速で、計算量は O(log n) になります。

ここでは、再帰呼び出しを利用したJavaScriptの二分探索関数 binarySearch() を作成します。この関数は次の4つの引数を受け取ります。

• ソート済みの数値・文字列の配列
• 配列の開始インデックス（0）
• 配列の終了インデックス（length - 1）
• 検索したい値

値が配列内に存在する場合はそのインデックスを返し、存在しない場合は -1 を返します。それでは、完全なコードを見ていきましょう。

コード例

const arr = [2, 4, 6, 6, 8, 8, 9, 10, 13, 15, 17, 21, 24, 26, 28, 36, 58, 78, 90];

// 二分探索関数
// 見つかった場合は要素のインデックスを、見つからない場合は -1 を返す
const binarySearch = (arr, start, end, num) => {
    const mid = start + Math.floor((end - start) / 2);
    if (start <= end) {
        if (arr[mid] === num) {
            return mid;
        }
        if (num < arr[mid]) {
            return binarySearch(arr, start, mid - 1, num);
        }
        if (num > arr[mid]) {
            return binarySearch(arr, mid + 1, end, num);
        }
    }
    return -1;
};

console.log(binarySearch(arr, 0, arr.length - 1, 13));
console.log(binarySearch(arr, 0, arr.length - 1, 11));

実行結果

このコードをコンソールで実行すると、次のように出力されます。

8
-1

最初の呼び出しでは値 13 がインデックス 8 の位置に存在するため 8 が出力され、2回目の呼び出しでは 11 が配列内に存在しないため -1 が出力されます。

アルゴリズムの仕組み

この二分探索は、次の手順で動作します。

1. start + Math.floor((end - start) / 2) によって、探索範囲の中央インデックスを求めます。
2. 中央の要素が検索対象と一致したら、そのインデックスを返します。
3. 検索対象が中央の要素より小さい場合は、左半分の範囲に対して再帰的に探索を続けます。
4. 逆に大きい場合は、右半分の範囲に対して再帰的に探索します。
5. 開始インデックスが終了インデックスを超えた時点で値が存在しないと判断し、-1 を返します。

探索のたびに対象範囲が半分になるため、要素数 n の配列でも最大約 log₂n 回の比較で検索が完了します。たとえば100万件のデータなら20回前後の比較で済むため、大規模なデータセットの検索において非常に効果的な手法です。