二分探索とは？
にぶんたんさく
二分探索とは、整列済みのデータ列に対して、探索範囲を半分ずつ絞り込みながら目的の値を効率よく見つけるアルゴリズムです。
二分探索（Binary Search）とは、あらかじめ昇順または降順に並べられたデータ列の中から、特定の値を高速に見つけ出すアルゴリズムです。「二分法」とも呼ばれます。
仕組みは非常にシンプルです。まず探索範囲の中央の要素と目的の値を比較します。目的の値が中央より小さければ左半分を、大きければ右半分を次の探索範囲とします。この操作を繰り返すことで、探索範囲が毎回半分に絞られていきます。
計算量はO(log n)であり、100万件のデータでも最大20回程度の比較で目的の値に到達できます。一方、先頭から順に調べる線形探索はO(n)のため、データ量が増えるほど二分探索の優位性が際立ちます。
二分探索の適用条件と特徴をまとめると以下のとおりです。
- データが事前にソートされていることが必須
- 配列などのランダムアクセスが可能な構造に適している
- 辞書・電話帳・索引検索など、実世界でも広く応用される
- 競技プログラミングでは答えの候補範囲に適用する「答えで二分探索」の手法も頻出
プログラミング言語の標準ライブラリにも多くの場合組み込まれており、PythonのbisectモジュールやC++のstd::binary_searchなどが代表例です。
使い方・例文
辞書で単語を調べるとき、まず真ん中のページを開いて目標の文字と比較し、前後どちらかに絞ってページをめくる動作は、二分探索の直感的な例です。
この用語をシェア
最終更新: