二分探索とは？

詳細解説

二分探索（バイナリサーチ）は、**昇順または降順にソートされた配列**に対して、中央の要素と目的値を比較し、目的値が小さければ左半分、大きければ右半分に探索範囲を絞り込む操作を繰り返すアルゴリズムです。1回の比較で探索範囲が半分になるため、計算量はO(log n)であり、線形探索のO(n)と比べて大規模データで圧倒的に高速です。例えば100万件のデータでも最大約20回の比較で見つかります。実装上の重要ポイントは「left, right, mid」の3変数で探索範囲を管理し、`mid = (left + right) / 2`（整数除算）で中央添字を計算することです。FE試験では「ソート済みが前提」「mid計算のオーバーフロー（left + (right - left) / 2推奨）」「終了条件（left > rightまたはleft >= right）」が出題ポイントです。疑似言語での実装トレースでは、各ステップの変数値の変化を丁寧に追うことが正答の鍵です。

FE試験での出題ポイント

• 1前提：昇順（または降順）ソート済みの配列が必須
• 2計算量O(log n)：100万件でも約20回比較で完了
• 3left/right/mid 3変数のトレース練習が最重要
• 4線形探索との比較：ソート要否・計算量・適用場面の違い

関連用語