†2分探索法とは、検索対象がソートされている場合に適用できる高速な検索手法のことである。2分探索法は、具体的には次のようなアルゴリズムで検索を行う。検索の開始は、真ん中に位置するデータと比べる。一致すればそれで終わりである。小さければ目的のデータは前半にあり、大きければ後半にある。これをデータが無くなるまで繰り返す。この手法の胆は、検索範囲を2分割することで、検索対象が一気に絞り込まれるところにある。1000個のデータに対しては多くても10回程度の比較により結果が得られる。一般にN個のデータから検索する場合にはlog2N回のオーダーの比較で目的とするデータが得られる。この方法がすごいのは、要素数が倍になっても繰り返しは一回しか増えないことです。n)のアルゴリズムということです。これがどれほどすごいかというと、たとえ100万要素あっても、たかだか20回程度の繰り返しで済む。