バイナリー‐サーチ【binary search】
読み方:ばいなりーさーち
⇒二分探索
にぶん‐たんさく【二分探索】
読み方:にぶんたんさく
《binary search》データ検索の手法の一。ソートされたデータ列から目的とするデータを検索する際、まずデータ列の中央の値と大小比較をし、目的とするデータがどちらにあるかを判断する。この作業を、目的のデータがあるとされた半分のデータ列に対して繰り返し行うことにより、目的とするデータを検索する。二分検索。バイナリーサーチ。
にぶん‐けんさく【二分検索】
読み方:にぶんけんさく
《binary search》⇒二分探索
2分探索法
別名:バイナリサーチ
【英】binary search
2分探索法とは、検索対象がソートされている場合に適用できる高速な検索手法のことである。
2分探索法は、具体的には次のようなアルゴリズムで検索を行う。まず、検索の開始は、真ん中に位置するデータと比べる。一致すればそれで終わりである。小さければ目的のデータは前半にあり、大きければ後半にある。これをデータが無くなるまで繰り返す。
この手法の胆は、検索範囲を2分割することで、検索対象が一気に絞り込まれるところにある。1000個のデータに対しては多くても10回程度の比較により結果が得られる。一般にN個のデータから検索する場合にはlog2N回のオーダーの比較で目的とするデータが得られる。
なお、この手法はデータが整列していることが前提のため、データの変更が多い状況では、その準備のためのソートにかかる時間により、かえって全体の効率が落ちる場合がある。
- binary searchのページへのリンク