2分探索法

IT用語辞典バイナリ

2分探索法

読み方：にぶんたんさくほう
別名：バイナリサーチ
【英】binary search

2分探索法とは、検索対象がソートされている場合に適用できる高速な検索手法のことである。

2分探索法は、具体的には次のようなアルゴリズムで検索を行う。まず、検索の開始は、真ん中に位置するデータと比べる。一致すればそれで終わりである。小さければ目的のデータは前半にあり、大きければ後半にある。これをデータが無くなるまで繰り返す。

この手法の胆は、検索範囲を2分割することで、検索対象が一気に絞り込まれるところにある。1000個のデータに対しては多くても10回程度の比較により結果が得られる。一般にN個のデータから検索する場合にはlog₂N回のオーダーの比較で目的とするデータが得られる。

なお、この手法はデータが整列していることが前提のため、データの変更が多い状況では、その準備のためのソートにかかる時間により、かえって全体の効率が落ちる場合がある。

情報処理のほかの用語一覧

アルゴリズム：

スタック  2分木  2分探索木  2分探索法  探索法  単純挿入法  単純選択法

>>アルゴリズムカテゴリの他の用語

ウィキペディア

二分探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/03 08:05 UTC 版)

探索 > 二分探索

二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。

概要

ソート済みのリストや配列に入ったデータ（同一の値はないものとする）に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。

n個のデータがある場合、時間計算量は${\displaystyle O(\log _{2}n)}$