二分探索 【binary search】 2分探索 / バイナリサーチ

概要

解説 まず、データを降順（大きい順）あるいは昇順（小さい順）に並べ替え、探索したいデータが中央の要素より大きいか小さいかを調べる。これにより、データが全体の前半分にあるか後ろ半分にあるかを判定することができるため、存在しない側の半分は探索範囲から外すことができる。

半分になったデータ群の中央の要素と再び比較し、前半と後半のどちらにあるかを調べる。この操作を繰り返し行うことで、一回の操作ごとに探索範囲の大きさが半分になっていき、中央の要素が求めるデータに一致するか、探索範囲の要素数が一つになる（求めるデータは見つからなかったことが確定する）と探索は終了する。

値の大小は文字の索引順の前後関係などに適宜置き換えることにより、順序と比較手段を定義できればどのようなデータにも適用することができる。

n個のデータ群から平均でlog₂n回の比較で探索を終えることができ、例えば1000個のデータを10回の比較で探索できる。原理は単純ながら高速なアルゴリズムである。ただし、要素があらかじめ整列済みである必要があるため、未整列のデータに適用するにはソートの分の計算時間も必要となる。