JavaScriptでソート済み配列から要素を高速に検索する最適な方法：二分探索の実装

ソート済みの配列（昇順・降順は問わない）から特定の値を探す場合、二分探索（バイナリサーチ）が最も最適化された、効率的な検索アルゴリズムとして広く知られています。先頭から順に比較していく線形探索が O(n) の計算量を必要とするのに対し、二分探索は O(log n) で完了するため、大規模なデータセットでも非常に高速に動作します。

この記事では、リテラルのソート済み配列からターゲットとなる値を検索する二分探索関数を実装します。さらに、その関数を Array.prototype に追加することで、すべての配列インスタンスから直接メソッドとして呼び出せるようにする方法を紹介します。

実装例

実際のコードは以下の通りです。

const arr = [2, 5, 8, 12, 14, 16, 17, 22, 26, 28, 35, 67, 78, 99];
const target = 22;
Array.prototype.binarySearch = function(target) {
    if ( !this.length ) { return false; }
    if ( this[0] === target ) { return true; }
    var i, mid,
        start = 0,
        end = this.length,
        c = false;
    while ( c = (i = this[mid = start+((end-start)>>1)]) !== target ) {
        i < target ? (start = mid) : (end = mid);
        if (start >= end - 1) { break; }
    }
    return !c;
};
console.log(arr.binarySearch(target));

コードの仕組み

この二分探索関数の処理の流れは以下の通りです。

• まず、配列が空の場合は即座に false を返します。
• 探索範囲の開始位置 start と終了位置 end を設定します。
• ループごとに、中央のインデックス mid を計算します。ここではビットシフト演算子 >> 1 を使うことで、2で割った商を効率的に求めています。
• 中央の値がターゲットより小さければ start を中央へ移動し、大きければ end を中央へ移動して、探索範囲を半分に絞り込みます。
• ターゲットが見つかれば true、探索範囲を使い切って見つからなければ false を返します。

実行結果

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

true

この例では、14個の要素を持つ配列から 22 をわずか数回の比較で見つけ出しています。このように、二分探索を Array.prototype に追加しておけば、どの配列に対しても簡潔な記述で高速な検索を行えるようになります。