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

二分探索の比較回数【午前解説】

正解の理由

解法ステップ

1. 比較回数を $T(n)$ とする。探索で1回比較すると残りは最大 $n/2$ 個に減る。
2. 再帰的関係式：$T(n)=T(\lfloor n/2\rfloor )+1$（$n>1$）。
3. この漸化式を展開すると $T(n)=1+1+1+\cdots$ を $k$ 回繰り返し、$n/2^k\approx 1$ となる $k$ が必要。
4. すなわち $2^k\approx n$ で $k\approx {\log }_{2}n$。従って比較回数は $O(\log n)$、およそ ${\log }_{2}n$ 回となる。
5. 最悪ケースは添字や端条件により $\lfloor {\log }_{2}n\rfloor +1$ 回と表現されることが多い。

選択肢別の誤答解説

• ア: ${\log }_{2}n$ — 正解。半分に絞る操作を行う二分探索の比較回数を表す最もふさわしい式です。
• イ: $({\log }_{2}n+1)/2$ — 誤り。比較回数の「平均」をこのように単純に半分にする根拠はなく、中央からの距離の平均と混同した誤りです。
• ウ: $n$ — 誤り。これは線形探索の比較回数（最悪 $n$ 回）であり、半分に分割する二分探索の性質と矛盾します。
• エ: $n^2$ — 誤り。二分探索は二重ループによる二次時間ではなく、むしろ対数時間で解ける問題です。

よくある誤解

• 「(log2 n + 1)/2 が平均値」：中央からの距離平均を誤って取るとこの式に行き着くが、比較回数の期待値は探索の成否や確率分布で異なり一般式ではない。
• 「底が重要で10やeの対数を使うべき」：複雑度の観点では対数の底は定数因子に過ぎず、二分探索では半分にするので底は 2 を用いるのが自然。
• 「線形探索と同じ $n$ や二重ループだから $n^2$」：二分探索は範囲絞り込みで高速化されるため線形や二次とは本質が異なる。

補足コラム

• 具体例：$n=1$ のとき比較は 1 回、$n=2$ で最大 2 回、$n=8$ の最悪比較回数は $\lfloor {\log }_{2}8\rfloor +1=4$ 回です。
• 成功検索と失敗検索で比較回数が異なる点に注意。成功検索の平均比較回数は位置分布に依存しますが、最悪は上記の式が目安です。
• ビッグオー表記では $O(\log n)$ と表現し、底は定数因子の違いとして無視できます。実装（再帰／反復）による回数差は僅少です。

FAQ