基本情報技術者 2015年 春期 午前（科目A） 問06

二分探索法の計算量【午前解説】

正解の理由

解法ステップ

1. 初期の候補数を $n$ とする。1 回の比較で候補は約半分になる。
2. $k$ 回比較した後の候補数は概ね $n/2^k$ となる。
3. 探索が終了するのは候補数が 1 以下になったときなので $n/2^k\le 1$ を解く。
4. この不等式から $2^k\ge n$、すなわち $k\ge {\log }_{2}n$。したがって必要な比較回数は $O(\log n)$ である。
5. 定数や端数（切り上げや +1 のオフセット）はオーダーには影響しないため最終的に $O(\log n)$ と表現する。

選択肢別の誤答解説

• ア: ア（$\log n$） — 正解。二分探索の比較回数は対数オーダーで表されます。
• イ: $n$ — 誤り。線形探索（未整列・逐次探索）では $O(n)$ ですが、二分探索は整列済みで毎回半分に絞れるため該当しません。
• ウ: $n^2$ — 誤り。二重ループや比較ソートの最悪ケースなど二次時間アルゴリズムの表現であり、二分探索とは無関係です。
• エ: $n\log n$ — 誤り。これは高速ソート（マージソートやヒープソート等）の時間オーダーで、探索単体の二分探索とは異なります。

よくある誤解

• 「探索は $O(n)$ ではないか」
  未整列で線形探索を行う場合は $O(n)$ ですが、二分探索は整列済みを前提にしているため $O(\log n)$ になります。前提条件の見落としが多いです。
• 「底の違い（${\log }_2$ か ${\log }_{10}$ か）で選択が変わる」
  底は定数因子にすぎず、オーダー記法では無視できます。試験では単に対数である点を重視してください。
• 「再帰だと遅くなるので $n\log n$ または $n^2$ になる」
  再帰/反復は実装差であり、計算量のオーダー自体は変わりません。アルゴリズムの本質を混同しないこと。

補足コラム

• 厳密な比較回数: 要素数 $n$ に対する最悪比較回数は一般に $\lfloor {\log }_{2}n\rfloor +1$（記法や実装によっては切り上げ）となりますが、オーダーは $\Theta (\log n)$ です。
• 前提条件の重要性: 二分探索は「整列されていること」が必須です。整列されていない配列で使うと誤った結果になります。
• 応用: 平衡二分探索木やバイナリサーチを利用する標準ライブラリの lower_bound/upper_bound も計算量は $O(\log n)$ です。
• 実装注意: 再帰実装でもループ実装でも計算量は同じですが、実装でのインデックスオーバーフローや中間計算のオフバイワンに注意してください。

FAQ