二分探索とは？

二分探索（バイナリサーチ）とは、整列済みのデータに対して、真ん中の値と比べて「大きい／小さい」で探す範囲を毎回半分に捨てていく探索方法です。

1回の比較で候補が半分になるので、データが2倍に増えても手数は1回増えるだけ。計算量は O(log n) で、100万個でも約20回で見つかります。先頭から1つずつ見る線形探索（O(n)）とは桁違いの速さです。

図：真ん中と比べて「大きい／小さい」で毎回半分を捨てる。事前に整列されているのが前提

ただし事前にデータが整列されている必要があるのが前提条件。この「探す前に並べておく」考え方を木構造で実現したのが2分探索木です。

基本情報技術者試験では、整列が前提であること、計算量 O(log n)、比較回数（2の何乗で範囲を絞れるか）が問われます。