二分探索とは

二分探索とは、整列済みのデータの中央の要素と目的の値を比べ、目的の値がある側の半分に範囲を絞る操作を繰り返して探す方法である。

1回の比較で探索範囲が半分になるため、n件のデータでの最大比較回数は ⌊log₂n⌋＋1 回程度となり、計算量はO(log n)である。先頭から順に調べる線形探索（O(n)）よりも、データが多いほど効率がよいが、データがあらかじめ整列されている必要がある。