2分探索(ニブンタンサク)とは | 意味や読み方など丁寧でわかりやすい用語解説

2分探索（バイナリサーチ）は、ソート済みのデータ集合の中から目的の要素を効率的に探し出すための探索アルゴリズムである。このアルゴリズムは、探索範囲を段階的に半分に絞り込んでいくことで、非常に高速に目的の要素を見つけ出すことができる特徴を持つ。大量のデータの中から特定の情報を見つけ出す必要がある場面において、その高速性から多用される基本的なアルゴリズムの一つとして認識される。例えば、電話帳から特定の人物の名前を探す際や、辞書から単語を引く際、あるいはデータベースで特定のレコードを検索する際など、データが何らかの順序で並んでいる場合に特にその真価を発揮する。ただし、このアルゴリズムを適用するためには、対象となるデータが必ず事前にソートされている（昇順または降順に並べ替えられている）必要があるという厳密な前提条件がある。

2分探索の具体的な手順は以下の通りである。まず、探索対象となるソート済みデータの「最も左の要素」と「最も右の要素」を指すポインタ（またはインデックス）を設定し、この2つのポインタが囲む範囲が現在の探索範囲となる。次に、この探索範囲の中央に位置する要素を特定する。中央要素のインデックスは、一般的に左端のインデックスと右端のインデックスを足して2で割ることで算出できる。

中央の要素が特定できたら、その要素の値と、探している目的の値（探索対象値）を比較する。比較の結果には三つのケースが考えられる。

第一に、中央の要素の値が探索対象値と完全に一致した場合、目的の要素が見つかったことになるため、探索はここで終了し、目的の要素の存在を返す。

第二に、中央の要素の値が探索対象値よりも大きい場合、データはソートされているため、目的の要素は中央の要素よりも左側の範囲に存在することが確定する。中央より右側の要素はすべて中央の要素以上の値を持つからである。この場合、探索範囲を中央の要素のすぐ左側から左端までの範囲に絞り込み、右端のポインタを中央の要素の左隣に移動させる。

第三に、中央の要素の値が探索対象値よりも小さい場合、同様にデータがソートされているため、目的の要素は中央の要素よりも右側の範囲に存在することが確定する。中央より左側の要素はすべて中央の要素以下の値を持つからである。この場合、探索範囲を中央の要素のすぐ右側から右端までの範囲に絞り込み、左端のポインタを中央の要素の右隣に移動させる。

このプロセスを、探索範囲がなくなるまで（すなわち、左端のポインタが右端のポインタよりも大きくなるまで）繰り返す。探索範囲がなくなったにもかかわらず目的の要素が見つからなかった場合、その要素はデータ集合の中に存在しないと判断し、探索は失敗となる。

2分探索の効率性は、その計算量（オーダー）によって示される。データ数をnとした場合、2分探索の計算量はO(log n)である。これは、一回の比較ごとに探索範囲が約半分になるため、n個のデータに対して最大でもlog₂n回の比較で探索が完了することを意味する。例えば、100万個のデータがあったとしても、約20回（log₂1,000,000 ≈ 19.9）の比較で目的の要素に到達できる可能性がある。これに対し、先頭から順に一つずつ調べていく線形探索（リニアサーチ）の計算量はO(n)であり、同じ100万個のデータでは最悪100万回の比較が必要となるため、2分探索がいかに高速であるかが理解できる。

2分探索の主なメリットは、その圧倒的な探索速度にある。特に大規模なデータセットに対しては、線形探索と比較して劇的な性能向上をもたらす。また、実装が比較的シンプルであり、配列のような連続したメモリ領域に格納されたデータに対して容易に適用できる点も利点である。

一方でデメリットも存在する。最大のデメリットは、探索対象のデータが事前にソートされている必要がある点である。データがソートされていない場合、まずソート処理を実行する必要があり、そのソートにかかる時間が探索のメリットを相殺してしまう可能性がある。データが頻繁に追加、削除されるようなケースでは、その都度データをソートし直すか、ソート状態を維持するためのコスト（例: 挿入時に適切な位置を見つけて要素を移動させる、削除時に空いた穴を詰める）が発生するため、2分探索は必ずしも最適な選択とはならない場合がある。このような場合は、ソート済みの状態を常に維持しながら探索を行う二分探索木のようなデータ構造が検討されることが多い。

実装上の注意点としては、中央要素のインデックスを計算する際に、左端と右端のインデックスの合計が非常に大きな値になり、整数のオーバーフローを引き起こす可能性がある点がある。これを避けるためには、多くのプログラミング言語で採用される (left + right) / 2 の代わりに left + (right - left) / 2 のような計算式を用いることで、中間結果の最大値を抑えることができる。

2分探索は、単に配列から要素を探すだけでなく、特定の条件を満たす最小値や最大値を探索する問題、あるいは数値解析における方程式の根を探索する「二分法」など、様々な場面に応用されている。その基本的な考え方は、多くのアルゴリズムやデータ構造の基盤となっており、システムエンジニアを目指す上で理解しておくべき重要な概念である。