テクノロジ系出題頻度 3/3
二分探索
にぶんたんさく
定義
整列済みデータを中央値と比較して半分ずつ探索範囲を絞り込む探索法。計算量O(log n)。
詳細解説
バイナリサーチ。データが昇順または降順に整列されていることが前提。中央要素と目的値を比較し、目的値が小さければ前半、大きければ後半に範囲を絞る操作を繰り返す。各ステップで範囲が半分になるためO(log n)。整列コストO(n log n)を払えれば、繰り返し検索する状況で大きな効果。再帰または反復で実装でき、配列・二分探索木で同じ原理が利用される。事前に整列されていない場合は線形探索の方が有利。
「二分探索」が出る問題
関連用語
よくある質問
Q. 二分探索とは何ですか？
A. 整列済みデータを中央値と比較して半分ずつ探索範囲を絞り込む探索法。計算量O(log n)。
Q. 応用情報技術者試験での位置づけは？
A. テクノロジ系の重要用語です。出題頻度は 3/3 （★3）。 頻出のため確実に押さえておきましょう。