テクノロジ
二分探索とは
英語名：Binary Search
ひとことで言うと：整列済みデータの中央要素と比較し、探索範囲を半分ずつ捨てながら目的値を探す方法。
意味をわかりやすく解説
二分探索では、中央値より目的値が小さければ左半分、大きければ右半分だけを次の探索対象にします。比較するたびに候補数がおよそ半分になるため、大量データを効率よく探索できます。
要素数nに対して計算量はO(log n)です。ただし、対象がキー順に整列されていることが前提です。配列など中央要素へ直接アクセスできる構造と相性が良い方法です。
具体例
1024件の整列済みデータなら、1024=2^10なので、探索範囲を10回程度半分にすると1件まで絞れます。
似た用語との違い
線形探索
二分探索は整列が必要で範囲を半減します。線形探索は並びに関係なく一件ずつ確認します。
基本情報技術者試験の試験ポイント
整列済みという前提とO(log n)を押さえます。候補が毎回半分になることから比較回数を見積もれます。
CHECK QUESTION
約100万件（2^20件）の整列済みデータを二分探索すると、最悪の比較回数はおよそ何回程度ですか。
答えを見る
約20回程度です。比較するたびに探索範囲がおよそ半分になるためです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。