二分探索

2025年10月20日

二分探索

英語表記: Binary Search

概要

二分探索（Binary Search）は、「探索アルゴリズム」の分野において、ソート（整列）されたデータ群の中から目的の値を探し出すための、非常に効率的な手法です。これは、探索範囲を常に半分に絞り込みながら進めるのが特徴で、大量のデータの中からでも驚くほど高速に目的の値を見つけ出すことができる優れたアルゴリズムです。私たちがデータ処理の効率、つまり「アルゴリズムと計算量」を考える上で、絶対に欠かせない基礎技術の一つと言えますね。

詳細解説

探索アルゴリズムとしての目的と前提

二分探索が他の探索アルゴリズム（例えば線形探索）と決定的に異なる点は、その前提条件と性能にあります。

前提条件：
二分探索を行うためには、対象となるデータ群が必ずあらかじめ昇順または降順にソートされている必要があります。この制約があるからこそ、このアルゴリズムは高速に動作できるのです。もしデータがバラバラに並んでいたら、二分探索は適用できません。この前提は「探索アルゴリズム」を学ぶ上で非常に重要なポイントですので、ぜひ覚えておいてください。

動作原理：探索範囲の劇的な削減
二分探索の基本的な動作は非常にシンプルですが、その効果は絶大です。

中央値の特定: まず、現在の探索範囲のちょうど真ん中にある要素（中央値）を選び出します。
比較: 探したい目的の値と、特定した中央値を比較します。
範囲の絞り込み:
- もし目的の値が中央値よりも小さければ、目的の値は中央値より左側の範囲（前半）にしか存在しないことが確定します。
- もし目的の値が中央値よりも大きければ、目的の値は中央値より右側の範囲（後半）にしか存在しないことが確定します。
再帰: 新しく絞り込まれた半分の範囲に対して、再びステップ1から3を繰り返します。

このプロセスを繰り返すことで、一度の比較で探索対象のデータ量を半分に減らすことができます。これは、まるで広大な土地から宝物を見つける際に、毎回「この道の左半分には絶対にない！」と断言しながら進めるようなものです。

アルゴリズムと計算量：O(log n)の威力

二分探索が「アルゴリズムと計算量」という上位カテゴリで高く評価される最大の理由は、その驚異的な計算効率、すなわち計算量O(log n)（オーダー・ログ・エヌ）にあります。

O(log n)とは、データ数 $n$が増加しても、必要な処理回数（比較回数）は対数的にしか増えないことを意味します。具体的に見てみましょう。

| データ数 $n$ | 線形探索（最悪O(n)）の比較回数 | 二分探索（最悪O(log₂ n)）の比較回数 |
| :—: | :—: | :—: |
| 10個 | 10回 | 約4回 |
| 1,000個 | 1,000回 | 約10回 |
| 1,000,000個 | 1,000,000回 | 約20回 |

ご覧の通り、データが100万個あっても、二分探索なら最悪20回程度の比較で済んでしまうのです！線形探索（最初から順に見ていく方法）では100万回かかるところを、たった20回で完了できるというのは、まさに魔法のような効率ですよね。この圧倒的な性能差こそが、私たちが大規模データ処理において二分探索を学ぶ理由です。

実装上のキーコンポーネント

二分探索の実装においては、主に以下の3つのポインタ（またはインデックス）を管理しながら探索範囲を制御します。

Low (L)：現在の探索範囲の開始位置（最小インデックス）。
High (H)：現在の探索範囲の終了位置（最大インデックス）。
Mid (M)：中央値の位置。通常は (L + H) / 2 で計算されます。

この L と H を適切に更新し、探索範囲を狭めていくループ構造が、二分探索の核となります。

具体例・活用シーン

二分探索の原理は、私たちの日常生活の中にも実はたくさん隠れています。この「探索アルゴリズム」の概念を理解するために、身近な例で考えてみましょう。

1. 電話帳や辞書を引くときの無意識の行動（比喩）

皆さんが分厚い辞書で特定の単語を探すとき、最初から「あ」のページをめくることはありませんよね。

ページを開く: まず、辞書を真ん中あたりで開き、「き」のページだとします。
比較: 探している単語が「ま」だったら、「き」よりも後（右側）にあると判断し、左半分は即座に捨てます。
再度のオープン: 残りの右半分をさらに真ん中で開き、「た」のページだとします。
比較: 探している単語「ま」は「た」よりも後（右側）にあると判断し、さらに探索範囲を半分に絞り込みます。

この「真ん中を開く→比較する→半分を捨てる」という動作こそが、まさに二分探索そのものです。データ（辞書の内容）があらかじめ五十音順にソートされているからこそ可能な、非常に効率的な探索方法なのです。

2. 数当てゲーム（ストーリー）

友人と「1から100までの整数を一つ決めて、私が当てる」というゲームをするときの戦略も二分探索です。

探索者（私）の思考プロセス:

1回目: 「50ですか？」→ 友：「もっと大きい」
- これで探索範囲は [51, 100] に絞られました。
2回目: 「75ですか？」→ 友：「もっと小さい」
- 探索範囲は [51, 74] に絞られました。
3回目: 「62ですか？」→ 友：「もっと大きい」
- 探索範囲は [63, 74] に絞られました。

データ数 $n=100$の場合、線形探索だと最悪100回かかりますが、二分探索なら $\log_2 100 \fallingdotseq 6.64$ なので、たった7回以内で必ず当てることができます。このストーリーを通じて、二分探索の効率の良さを実感していただけると嬉しいです。

3. 実際のIT分野での活用シーン

データベースのインデックス探索: データベースのレコードは、高速な検索のためにインデックス（索引）がソートされて保持されています。特定のキーを持つレコードを高速に探し出す際、このインデックスに対して二分探索が適用されます。
APIの検索: 特定のIDや名前を持つユーザーをリストから探す際など、事前にソートされたデータ構造（配列やリスト）に対して広く利用されます。
境界値の特定: ある条件を満たす最小値や最大値を特定する際（例：ある関数が正の値を取る境界点を探す）にも、二分探索の考え方が応用されます。

資格試験向けチェックポイント

二分探索は、「アルゴリズムと計算量」および「探索アルゴリズム」の分野で最も頻出するテーマの一つです。ITパスポートから応用情報技術者試験まで、様々なレベルで出題されます。

ITパスポート・基本情報技術者試験レベル

必須条件の理解: 二分探索が適用できるのはデータがソートされている場合のみであることを必ず覚えてください。これは探索アルゴリズムの基本中の基本です。
線形探索との比較: 線形探索（O(n)）と二分探索（O(log n)）の効率の違いを理解し、なぜ二分探索が高速なのかを説明できるようにしておきましょう。特にデータ数が多いほど差が開くことを理解することが重要です。
基本的な動作原理: 毎回探索範囲を半分に絞り込むという仕組みを、例題を通じて確認してください。何回で探索が完了するかを計算させる問題がよく出題されます。
前処理の必要性: 二分探索を適用する前に、データをソートする「整列アルゴリズム」が必要になるという点も、アルゴリズム全体の流れとして重要です。

応用情報技術者試験レベル

計算量の厳密な理解: O(log n)の意味を深く理解し、特に最悪計算量がなぜ対数になるのかを説明できるようにしてください。探索アルゴリズムの効率を問う記述問題で必須の知識となります。
擬似コードの読解: 二分探索のアルゴリズムを記述した擬似コード（ループ制御やインデックスの更新：L, H, M）を正確に読み解き、特定のデータに対するトレース（追跡）ができる能力が求められます。
応用: 単純な探索だけでなく、二分探索の考え方を応用した問題（例：配列内の特定の要素の挿入位置の探索、特定の値が何回出現したかのカウントなど）にも対応できるように準備しておくと良いでしょう。
前処理コストの考慮: ソート（O(n log n)）にかかる時間と探索（O(log n)）にかかる時間を総合的に判断し、データ更新が頻繁な場合に二分探索が常に最適とは限らない、といった考察も重要になります。