対象試験と出題頻度
2分探索法（バイナリサーチ）は、基本情報技術者・応用情報技術者で出題されるテーマです。
科目Aでは「最大比較回数を求める問題」や「2分探索の性質として正しいものを選ぶ問題」が定番化しており、科目Bでは擬似言語による探索処理のトレース問題として登場します。
線形探索法やハッシュ表探索法との計算量の違いを正確に答えられるかがポイントになります。
詳細をクリックして確認
基本情報技術者
応用情報技術者
★★★☆☆
ランクB（標準）覚えておくと有利
用語の定義
情報処理試験を勉強していると、「2分探索って線形探索と何が違うの？なぜ速いの？」と疑問に感じがちです。
2分探索法（Binary Search）とは、一言で言うと
「あらかじめ昇順または降順に整列されたデータ列に対し、中央の要素と目的値を比較して探索範囲を半分に絞る操作を繰り返すことで、高速にデータを見つけ出すアルゴリズム」
のことです。
イメージとしては、「辞書でページの真ん中を開き、目的の単語が前半か後半かを判断して絞り込む」こと。
最初から1ページずつめくるのではなく、毎回半分に絞ることで圧倒的に速くたどり着ける。これが2分探索法の考え方です。
📊 2分探索法の基本情報
| 項目 | 内容 |
|---|---|
| 英語名 | Binary Search（バイナリサーチ） |
| 前提条件 | データが昇順または降順に整列済みであること |
| 平均計算量 | O(log₂n) |
| 最大比較回数 | ⌊log₂n⌋ + 1 回 |
解説
線形探索法は先頭から1つずつ比較するため、データ件数に比例して処理時間が増えます（計算量 O(n)）。データ件数が数千、数万と増えると、この方法では現実的な速度を保てません。
2分探索法は「中央値との比較で探索範囲を半分に絞る」操作を繰り返すことで、データ件数が倍になっても比較回数は1回しか増えないという劇的な高速化を実現します。
ただし、データがあらかじめ整列されていることが絶対条件です。
探索の流れ
探索範囲の左端（low）と右端（high）を設定し、中央のインデックス mid = (low + high) / 2 を計算します。中央の要素と目的値を比較し、一致すれば探索終了です。
目的値のほうが大きければ low = mid + 1 に更新して後半だけを対象にし、小さければ high = mid − 1 に更新して前半だけを対象にします。この操作を low > high（探索範囲が空）になるまで繰り返します。
🔍 2分探索の動作イメージ（目的の値：7）
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| 配列 | 1 | 3 | 5 | 8 | 12 | 15 | 20 |
| ▲ 1回目：mid=3（値8）→ 7 < 8 なので前半へ | |||||||
| index | 0 | 1 | 2 |
| 配列 | 1 | 3 | 5 |
| ▲ 2回目：mid=1（値3）→ 7 > 3 なので後半へ | |||
| index | 2 |
| 配列 | 5 |
| ▲ 3回目：mid=2（値5）→ 7 ≠ 5、探索範囲が空 → 該当なし | |
7件のデータでも最大3回の比較で結論が出る（線形探索なら最大7回）
最大比較回数の求め方
n件の整列済みデータに対する2分探索の最大比較回数は ⌊log₂n⌋ + 1 回です。⌊ ⌋ は小数点以下を切り捨てるフロア関数（床関数）を意味します。
考え方はシンプルです。1回の比較で探索範囲が半分になるため、「n を何回 2 で割れば 1 以下になるか」を求めればよいのです。
📐 最大比較回数の計算例
| データ件数 n | ⌊log₂n⌋ + 1 | 最大比較回数 |
|---|---|---|
| 100 | ⌊6.64⌋ + 1 | 7回 |
| 1,000 | ⌊9.97⌋ + 1 | 10回 |
| 2,000 | ⌊10.97⌋ + 1 | 11回 |
| 1,000,000 | ⌊19.93⌋ + 1 | 20回 |
100万件でも最大20回で見つかる。2のべき乗（2¹⁰=1024 等）を覚えておくと即答できる。
▶ 2分探索の擬似コード（クリックで展開）
// 昇順に整列済みの配列 data[0..n-1] から値 key を探索
function binarySearch(data[], n, key)
low ← 0
high ← n - 1
while low ≦ high
mid ← (low + high) ÷ 2 // 小数点以下切り捨て
if data[mid] = key
return mid // 見つかった位置を返す
elseif data[mid] < key
low ← mid + 1 // 後半に絞る
else
high ← mid - 1 // 前半に絞る
endif
endwhile
return -1 // 見つからなかった
endループ1回ごとに探索範囲が半分になるため、計算量は O(log₂n) です。
線形探索法・ハッシュ表探索法との比較
2分探索法を正しく位置づけるには、他の手法との違いを「前提条件」と「計算量」で整理するのが近道です。
| 探索手法 | 平均計算量 | 前提条件 | 特徴 |
|---|---|---|---|
| 線形探索法 | O(n) | 整列不要 | 最もシンプル。少量データ向き |
| 2分探索法 | O(log₂n) | 整列済みであること | 中央値と比較し探索範囲を半分に絞る |
| ハッシュ表探索法 | O(1) | ハッシュ関数による格納 | 最速だがシノニム（衝突）の処理が必要 |
ここだけは確実に押さえてください。2分探索法は「整列済みデータが前提」「計算量 O(log₂n)」の2点がすべてです。線形探索法との最大の違いは「整列が必要かどうか」と「計算量の桁違いの差」です。
では、この用語が試験でどのように出題されるか見ていきましょう。
💡 2分探索法の核心を3行で
・整列済みデータの中央要素と目的値を比較し、探索範囲を半分に絞る操作を繰り返す
・最大比較回数は ⌊log₂n⌋ + 1 回（2,000件なら11回）
・線形探索法は「整列不要・O(n)」、2分探索法は「整列必須・O(log₂n)」と整理する
試験ではこう出る！
2分探索法は、基本情報技術者・応用情報技術者の科目Aで定番の出題テーマです。科目Bでも擬似言語を使った探索処理のトレースや穴埋め問題として繰り返し登場しています。
📊 過去問での出題実績
| 試験回 | 出題内容 | 問われたポイント |
|---|---|---|
| FE H26秋 午前 問6 |
2分探索に関する記述のうち適切なものを選ぶ問題。 | ・「データ列は整列されている必要がある」が正解 ・「常に線形探索より速い」はひっかけ ・H17秋FE問14と同一問題 |
| FE H20秋 午前 問13 |
2,000件の昇順データを2分探索するときの最大比較回数を求める問題。 | ・2¹⁰=1024、2¹¹=2048 から ⌊log₂2000⌋+1=11回 を導出 ・2のべき乗の暗記が前提 |
| FE H17春 午前 問15 |
データの個数が4倍になると最大探索回数がどう変化するかを問う問題。 | ・「2回増える」が正解 ・データ2倍→比較1回増、4倍→2回増の関係 |
| AP H25春 午前 問5 |
線形探索・2分探索・ハッシュ表探索の特徴の組み合わせを選ぶ問題。 | ・3つの探索手法の前提条件と計算量を正確に対比できるか |
📝 IPA試験での出題パターン
パターン1：「最大比較回数を求めよ」（科目A）
「n件のデータを2分探索する際の最大比較回数は？」と直接問う形式。2のべき乗（2¹⁰=1024、2¹¹=2048 など）を暗記しておけば即答できる。FE H20秋問13が代表例。
パターン2：「2分探索の性質として正しいものを選べ」（科目A）
ひっかけ選択肢の定番は「2分探索は線形探索より常に速い」。先頭付近に目的データがある場合は逐次探索のほうが比較回数が少ないため、「常に」は誤りとなる。
パターン3：「擬似言語で探索処理をトレースせよ」（科目B）
low・high・mid の変数更新を正確に追い、最終的な戻り値や比較回数を答える問題。IPAの科目Bサンプル問題 問13で出題済み。
試験ではここまででOKです。2分探索木（BST）やAVL木は別の論点なので、混同しないよう注意してください。
【確認テスト】理解度チェック
ここまでの内容を理解できたか、簡単なクイズで確認してみましょう。
Q. 2分探索法に関する記述として、最も適切なものはどれでしょうか？
- A. データの整列を必要とせず、先頭から末尾まで1つずつ順に比較するため、平均計算量は O(n) である。
- B. データが昇順または降順に整列されていることが前提であり、中央の要素と目的値を比較して探索範囲を半分に絞る操作を繰り返すため、平均計算量は O(log₂n) である。
- C. ハッシュ関数で算出したアドレスに直接アクセスして探すため、シノニムが発生しなければ平均計算量は O(1) であるが、データの整列が前提条件となる。
正解と解説を見る
正解：B
解説：
2分探索法は、整列済みデータに対して中央の要素と目的値を比較し、毎回探索範囲を半分に絞ることで O(log₂n) の計算量を実現するアルゴリズムです。整列されていないデータには適用できません。
選択肢Aは線形探索法の説明です。先頭から順に比較するため整列は不要ですが、計算量は O(n) で、データ件数に比例して処理時間が増加します。選択肢Cはハッシュ表探索法の説明に「データの整列が前提条件」という誤った条件を混入させたひっかけです。ハッシュ表探索は整列を前提としません。
よくある質問（FAQ）
Q. 「2分探索は線形探索より常に速い」が誤りなのはなぜですか？
目的データが配列の先頭付近にある場合、線形探索は1〜2回の比較で見つけられます。一方、2分探索は必ず中央から始めるため、先頭にあるデータを見つけるにも複数回の比較が必要です。「平均的には2分探索が圧倒的に速い」は正しいですが、「常に速い」は正しくありません。IPA試験ではこの違いがひっかけ選択肢として頻出します。
Q. 「2分探索法」と「2分探索木」は同じものですか？
別物です。2分探索法は「整列済みの配列に対する探索アルゴリズム」であり、2分探索木（BST: Binary Search Tree）は「各ノードが左の子＜親＜右の子の関係を持つ木構造のデータ構造」です。2分探索木はデータの挿入・削除が配列より柔軟に行える一方、木のバランスが崩れると探索性能が劣化します。試験では別の問題として出題されるため、混同しないよう注意してください。
Q. 2分探索法の弱点は何ですか？
最大の弱点は「データが整列されていないと使えない」点です。未整列のデータに適用するには、まずソート処理が必要になります。ソート自体の計算量が O(n log n) かかるため、探索が1回だけであれば、ソート＋2分探索よりも線形探索のほうがトータルで速い場合があります。同じデータに対して何度も探索を行う場面で、2分探索の真価が発揮されます。
Q. 試験で「2のべき乗」はどこまで覚えれば十分ですか？
2¹⁰ = 1,024 まで覚えておけば、ほとんどの出題に対応できます。IPA試験では「2,000件」「1,000件」のように1,024前後の数値が使われることが多いため、2¹⁰ = 1,024 を基準に上下を判断すれば最大比較回数を即答できます。余裕があれば 2²⁰ = 1,048,576（約100万）も覚えておくと安心です。
