2分探索法

2分探索法は、具体的には次のようなアルゴリズムで検索を行う。 まず、検索の開始は、真ん中に位置するデータと比べる。 一致すればそれで終わりである。 小さければ目的のデータは前半にあり、大きければ後半にある。 これをデータが無くなるまで繰り返す。 この手法の胆は、検索範囲を2分割することで、検索対象が一気に絞り込まれるところにある。 1000個のデータに対しては多くても10回程度の比較により結果が得られる。 一般にN個のデータから検索する場合にはlog2N回のオーダーの比較で目的とするデータが得られる。 なお、この手法はデータが整列していることが前提のため、データの変更が多い状況では、その準備のためのソートにかかる時間により、かえって全体の効率が落ちる場合がある。