【JavaScript】二分探索（バイナリサーチ）の実装方法：検索値が存在すればインデックスを返す

本記事では、ソート済みの数値配列を第1引数、検索したい数値を第2引数として受け取るJavaScript関数の実装方法を解説します。

検索対象の数値が配列内に存在する場合はそのインデックスを返し、存在しない場合は -1 を返します。この処理は二分探索（バイナリサーチ）アルゴリズムを用いて実装します。

二分探索とは？

二分探索は、典型的な分割統治法（Divide and Conquer）に分類されるアルゴリズムです。配列を半分ずつ再帰的（または反復的）に分割していき、探索範囲を絞り込みながら目的の要素へ収束させていきます。

なお、二分探索を行うには配列が事前にソートされている必要があります。ソート済みであることで、「中央の値と比較した結果から、次に探索すべきは左半分か右半分か」を簡単に判断できるためです。

実装コード

const arr = [-3, -1, 4, 7, 9, 11, 14, 22, 26, 28, 36, 45, 67, 78, 88, 99];

const binarySearch = (arr = [], num) => {
    let l = 0;
    let r = arr.length - 1;

    while (l <= r) {
        const mid = Math.floor((l + r) / 2);

        if (num === arr[mid]) {
            // 中央の値が検索値と一致 → インデックスを返す
            return mid;
        } else if (num < arr[mid]) {
            // 検索値が中央より小さい → 右端を左側へ移動
            r = mid - 1;
        } else {
            // 検索値が中央より大きい → 左端を右側へ移動
            l = mid + 1;
        }
    }

    // 見つからなかった場合
    return -1;
};

console.log(binarySearch(arr, 22));
console.log(binarySearch(arr, 56));
console.log(binarySearch(arr, 11));

コードのポイント

• ポインタ変数 l と r：それぞれ探索範囲の左端と右端のインデックスを表します。
• 中央インデックスの計算：Math.floor((l + r) / 2) で中央位置を求めます。
• 比較による範囲の絞り込み：検索値が中央の値より小さければ右端を mid - 1 に、大きければ左端を mid + 1 に更新し、探索範囲を半分に縮小します。
• ループ終了条件：l > r になった時点で探索範囲が消滅したことを意味するため、-1 を返して「見つからなかった」ことを示します。

実行結果

コンソールへの出力は以下のようになります。

7
-1
5

22 はインデックス7に存在するため 7、56 は配列内に存在しないため -1、11 はインデックス5に存在するため 5 がそれぞれ出力されます。

計算量について

二分探索の時間計算量は O(log n) です。線形探索（O(n)）と比べ、要素数が多い配列ほど圧倒的に高速に動作します。例えば、10億件のデータでも最大約30回の比較で検索が完了するため、大量データの検索において非常に有効な手法です。