【ITニュース解説】Everything You Need to Know About Binary Search

二分探索は、コンピューターがデータを効率よく見つけるための、非常に重要な技術の一つである。特に、たくさんのデータの中から特定の情報を見つけ出す際に、その威力を発揮する。この探索方法は、データを次々に半分に絞り込んでいく「分割統治」という考え方に基づいており、目的のデータを見つけるために必要な比較回数を劇的に減らすことができる。

まず、二分探索とはどのようなものか。これは、あらかじめ順番に並べられた（ソートされた）データの集まりの中から、探したいデータがどこにあるかを効率的に見つけ出すためのアルゴリズムである。データの並び順が昇順でも降順でも利用できるが、並んでいることが前提となる。もしデータがバラバラに並んでいる場合、一つずつ端から順番に見ていく「線形探索（リニアサーチ）」という方法を取ることになるが、これではデータ量が増えるにつれて非常に時間がかかってしまう。しかし、データがソートされている場合、二分探索を使えば、はるかに高速に目的のデータを見つけられるのだ。

二分探索はどのように動作するのか。例えば、昇順に並んだ数字の配列からある数字を探す場合を考えてみよう。まず、探索範囲のちょうど真ん中にある数字を取り出し、探している数字と比べる。もし真ん中の数字が探している数字と全く同じであれば、それが目的の数字であり、探索はそこで完了する。もし探している数字が真ん中の数字よりも小さい場合、目的の数字は真ん中の数字よりも左側の範囲にしかないことがわかる。なぜなら、配列は昇順に並んでいるからだ。反対に、探している数字が真ん中の数字よりも大きい場合、目的の数字は真ん中の数字よりも右側の範囲にしかないことになる。このようにして、一度の比較で探索すべき範囲を半分にまで減らすことができる。この半分に絞るという操作を、目的の数字が見つかるか、探索範囲がなくなるまで繰り返すのだ。具体的な例として、数字の配列 {23, 45, 50, 61, 81, 90, 100, 120} から数字の81を探す場合を考える。最初、配列の最初（インデックス0）を探索範囲の開始、最後（インデックス7）を終了とする。真ん中のインデックスは (0+7)/2 = 3 なので、配列の3番目の要素である61が真ん中の数字となる。探している81は61よりも大きいので、探索範囲を61の右側、つまりインデックス4から7までに絞り込む。次に、この新しい探索範囲 (4+7)/2 = 5 の要素である90が真ん中の数字となる。今度は探している81は90よりも小さいので、探索範囲を90の左側、インデックス4から4までに絞り込む。この範囲の真ん中はインデックス4で、要素は81である。これで目的の81が見つかった。この手順により、わずかな比較回数で目的の要素にたどり着くことができる。

アルゴリズムの効率性を測る指標として「時間計算量」がある。二分探索の時間計算量は、最良のケースと最悪のケースで異なる。最良のケースとは、配列のちょうど真ん中に探している数字が見つかる場合である。この場合、1回の比較だけで目的の数字が見つかるため、時間計算量はO(1)と表される。これは「定数時間」を意味し、データ量に関わらず常に同じ時間で処理が完了する、最も効率の良い状態を示す。一方、最悪のケースとは、探している数字が配列の端にある場合や、配列の中に存在しない場合である。この場合でも、二分探索は探索範囲を繰り返し半分にしていくため、必要な比較回数はデータの個数Nに対して非常に少ない。具体的には、探索範囲をNからN/2、N/4、N/8と減らしていき、最終的に1つの要素になるまで繰り返す。この繰り返し回数は、Nが2を何回かけ合わせた数になるか、つまりlog2(N)で表される。したがって、最悪ケースでの時間計算量はO(log N)となる。これは「対数時間」と呼ばれ、データ量が飛躍的に増えても処理時間の増加は緩やかであり、線形探索のO(N)に比べて圧倒的に高速である。例えば、100万個のデータがあったとしても、20回程度の比較で目的のデータを見つけ出すことができるのだ。

Javaでのコード実装を見ると、int middle = (start + end) / 2;という中間点の計算式に注意が必要だ。startとendが非常に大きな値の場合、その合計がint型で表現できる最大値を超えてしまい、意図しない値になる「オーバーフロー」が発生する可能性がある。これを避けるために、より安全な計算方法としてint middle = start + (end - start) / 2;が推奨される。この式ではend - startの差分を計算するため、大きな値の合計を避けることができる。

二分探索の基本は配列が昇順に並んでいることを前提としていたが、実際には降順に並んでいる場合もある。このような、どちらの順序でソートされているかを事前に気にせず探索できるアルゴリズムを「順序に依存しない二分探索（Order Agnostic Binary Search）」と呼ぶ。このアルゴリズムは、まず配列の最初と最後の要素を比較することで、配列が昇順なのか降順なのかを判断する。例えば、最初の要素が最後の要素より小さければ昇順、大きければ降順と判断する。この判断結果に基づいて、探索範囲を絞り込む方向（真ん中の要素より大きいなら右、小さいなら左、など）を適切に切り替える。この順序の判断にかかる時間はごくわずかであり、二分探索自体の効率性（時間計算量O(log N)）は変わらない。

二分探索は、単純な一次元の配列だけでなく、二次元の「行列（マトリックス）」の中での探索にも応用できる。もし行列が特にソートされていない場合、全ての行と列を一つずつ見ていくしかなく、行の数Mと列の数Nに対して時間計算量はO(M*N)となる。しかし、行列が「行ごとに昇順にソートされ、かつ列ごとに昇順にソートされている」といった特定の条件を満たしている場合、効率的な探索が可能になる。この場合、例えば行列の右上隅の要素から探索を始める戦略が有効だ。探している数字が現在の要素より小さい場合、その列のすべての要素は現在の要素より大きいため、現在の列を探索範囲から除外できる。もし探している数字が現在の要素より大きい場合、その行のすべての要素は現在の要素より小さいため、現在の行を探索範囲から除外できる。このようにして、一歩進むごとに探索範囲である行か列のどちらかを確実に減らしていくことができるのだ。この方法での時間計算量は、行列の行数と列数のうち少ない方に応じてO(N)となる。

さらに、行列全体が厳密にソートされている場合、例えば各行の最後の要素が次の行の最初の要素より小さいといった特殊な状況では、より高度な二分探索を適用できる。この場合、まず中央の列（または行）に二分探索を適用し、目的の要素が存在する可能性のある行（または列）を絞り込む。これにより、探索すべき範囲が少数の行に限定される。最終的に残った2つの行に対して、それぞれ通常の二分探索を適用することで、目的の要素を見つけ出す。この場合の時間計算量は、列の長さに対するlog Nと、残った行の長さに対するlog Mの合計となり、O(log N + log M)という非常に高速な探索が可能になる。

二分探索は、効率的なデータ探索の基本となる非常に強力なアルゴリズムである。システムエンジニアを目指す上で、このアルゴリズムの原理と具体的な動作、そして時間計算量の考え方を理解することは、問題解決能力を高め、より良いプログラムを設計するために不可欠となる。様々なデータ構造や状況において、どのように二分探索を適用できるかを学び、実践することで、プログラミングスキルの大きな向上に繋がるだろう。