二分探索

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

二分探索（binary search）は、ソート済みの配列やリストから特定の要素を効率的に検索するためのアルゴリズムです。このアルゴリズムは、探索範囲の中央にある要素を調べ、目的の値との大小関係に基づいて探索範囲を絞り込むという操作を繰り返します。これにより、線形探索よりも遥かに高速に要素を見つけ出すことができます。

二分探索の仕組み

1. 前提条件: 検索対象のデータ列が昇順または降順にソートされている必要があります。
2. 探索範囲: 最初はデータ列全体が探索範囲です。
3. 中央要素の確認: 探索範囲の中央にある要素を調べます。
4. 比較: 中央要素と目的の値とを比較します。
もし中央要素が目的の値と一致すれば、探索は終了です。
もし目的の値が中央要素よりも小さければ、探索範囲を中央要素の左側に絞ります。
もし目的の値が中央要素よりも大きければ、探索範囲を中央要素の右側に絞ります。
5. 繰り返し: 探索範囲がなくなるまで、ステップ3と4を繰り返します。

計算量

二分探索の計算量は、データ数nに対してO(log₂n)です。これは、探索範囲が繰り返し半分に絞られるため、データ数が大きくなっても検索時間がそれほど増大しないことを意味します。例えば、1000個のデータから検索する場合、二分探索では最大で10回程度の比較で済みます。

具体例

データが見つかる例

次のソート済み配列から25を探す例を見てみましょう。


[2, 3, 5, 7, 12, 18, 22, 25, 29, 32]


1. 初期状態では、配列全体が探索範囲です。
2. 中央の要素（12）と比較すると、25は12より大きいため、後半の範囲を探索します。
3. 後半の範囲の中央の要素（22）と比較すると、25は22より大きいため、さらに後半の範囲を探索します。
4. さらに後半の範囲の中央の要素（25）と比較すると、目的の値が見つかりました。探索終了です。

データが見つからない例(1)

次の配列から4を探す例を見てみましょう。


[2, 3, 5, 7, 12, 18, 22, 25, 29, 32]


1. 初期状態では、配列全体が探索範囲です。
2. 中央の要素（12）と比較すると、4は12より小さいため、前半の範囲を探索します。
3. 前半の範囲の中央の要素（3）と比較すると、4は3より大きいため、後半の範囲を探索します。
4. さらに範囲の中央の要素（5）と比較すると、4は5より小さいので左側を探索するはずですが、すでにそこには存在しないことがわかっています。探索範囲がなくなるため、データが見つからないという結果になります。

データが見つからない例(2)

次の配列から29を探す例を見てみましょう。


[2, 3, 5, 7, 12, 18, 22, 25, 27]

配列の一番右側の要素である27が29より小さいため、データが見つからないという結果になります。

実装上の注意点

二分探索を実装する際には、いくつかの注意点があります。特に、中央要素のインデックスを計算する際に、整数オーバーフローが発生しないように注意する必要があります。

中央のインデックスの計算は、`(left + right) / 2`ではなく、`left + (right - left) / 2`と記述するのが安全です。`left + right`が非常に大きな値になると、整数オーバーフローが発生する可能性があるからです。
Javaの標準ライブラリにある二分探索の実装にも、過去にこの問題があったことが知られています。

まとめ

二分探索は、ソート済みのデータから効率的に要素を検索する強力なアルゴリズムです。ただし、正しく実装するためにはいくつかの注意点があります。この記事が、二分探索の理解と実装の助けになれば幸いです。

関連項目

二分探索木
二分法

参考資料

Wikipedia - 二分探索

もう一度検索