C++プログラムにおける二分探索（バイナリサーチ）の基本と実装

二分探索（バイナリサーチ）とは

二分探索は「半区間探索」「対数探索」「バイナリチョップ」とも呼ばれる検索アルゴリズムで、ソート済みの配列の中から目的の値が存在する位置を効率的に見つけ出します。

基本的な仕組みは非常にシンプルです。まず、探したい値（ターゲット値）を配列の中央の要素と比較します。一致しなかった場合は、ターゲット値が存在し得ない半分を丸ごと排除し、残りの半分に対して同様の比較を繰り返します。この「中央との比較」と「範囲の絞り込み」を続け、ターゲット値が見つかるか、検索範囲が空になる（＝配列にその値が存在しない）かのどちらかで処理が終了します。

アイデア自体は簡単ですが、正しく実装するには終了条件や中間点の計算方法など、いくつかの細かい点への注意が必要です。特に、配列内の値が整数範囲全体を網羅していない場合には慎重な設計が求められます。

二分探索が選ばれる理由

二分探索は最も人気のある検索アルゴリズムの一つです。高速かつ効率的であり、さまざまな問題を解決する際に頻繁に活用される定番テクニックでもあります。

たとえば、世界中の人名をすべて順番に並べたリストから特定の名前の位置を探す場合でも、二分探索なら最大35回程度の反復で見つけ出すことができます。

前提条件：データがソートされていること

二分探索が機能するのは、要素がソートされた集合のみです。コレクションに二分探索を適用するには、事前に必ずソートしておく必要があります。

ソート済みの集合に対して二分探索を使用すれば、検索対象の値に応じて反復回数を常に削減できます。

具体例で理解する二分探索

次のような配列を考えてみましょう。

線形探索の場合、要素「8」の位置が判明するのは9回目の反復になります。

では、二分探索を使うと反復回数がどのように減るのかを見ていきましょう。検索を開始する前に、検索範囲の始まりと終わりを把握しておく必要があります。それぞれ「Low（下限）」「High（上限）」と呼びます。

Low = 0
High = n-1

次に、検索値 K を下限と上限の中間位置にある要素と比較します。K の方が大きければ下限を引き上げ、小さければ上限を引き下げます。

上の図では、下限が 0、上限が 9 です。

下限と上限の中間点は (lower_bound + upper_bound) / 2 = 4 となります。ここで a[4] = 4 です。この値 4 は、探している値 2 より大きいため、インデックス 4 より先の要素を調べる必要はありません。それ以降の要素は明らかに 2 より大きくなるからです。

したがって、配列の上限を要素 4 の位置まで切り詰めることができます。同じ手順を、次の範囲設定で再度適用します。

Low: 0
High: 3

この手順を再帰的に繰り返し、「Low > High」となった時点で終了します。途中の反復で a[mid] == key となれば mid の値を返します。これが配列内における key の位置です。key が配列に存在しない場合は -1 を返します。

C++による実装例

int binarySearch(int low, int high, int key){
    while(low <= high){
        int mid = (low + high) / 2;
        if(a[mid] < key){
            low = mid + 1;
        }
        else if(a[mid] > key){
            high = mid - 1;
        }
        else{
            return mid;
        }
    }
    return -1; // キーが見つからなかった場合
}