テクノロジ系出題頻度 2/3
二分探索
にぶんたんさく
定義
整列済みデータの中央と比較して探索範囲を半分に絞り込む高速な探索アルゴリズム。
詳細解説
バイナリサーチとも呼び、データが昇順または降順に整列されていることが前提。中央値と目的値を比較し、大小に応じて左右どちらかの半分のみを次の探索範囲とする。計算量はO(log n)で、要素数が2倍になっても比較回数が1回しか増えないため、大量データで威力を発揮する。例えば100万件でも約20回で見つかる。
「二分探索」が出る問題
関連用語
よくある質問
Q. 二分探索とは何ですか？
A. 整列済みデータの中央と比較して探索範囲を半分に絞り込む高速な探索アルゴリズム。
Q. IT パスポート試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 2/3 （★2）。 中程度の頻度で出題されます。