平成26年度 秋期 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズム2分探索に関する記述のうち，適切なものはどれか。
出典：平成26年度 秋期 基本情報技術者試験 午前 問6
- ア2分探索するデータ列は整列されている必要がある。
- イ2分探索は線形探索よりも常に速く探索できる。
- ウ2分探索は探索をデータ列の先頭から開始する。
- エn個のデータの2分探索に要する比較回数は，n log₂ n に比例する。
正解：ア
解説
2分探索は，整列済みのデータ列の中央の値と探索値を比較し，探索範囲を半分に絞り込んでいく方法です。整列されていないデータ列には適用できず，データ数nに対する比較回数はlog₂ nに比例します。
選択肢ごとの解説
- ア正しい。2分探索は中央値との大小比較で探索範囲を絞り込む方式であるため，あらかじめデータ列が整列されている必要があります。
- イ誤り。データ数が非常に少ない場合や特定の分布では，線形探索の方が速いこともあり，常に2分探索が速いとは限りません。
- ウ誤り。2分探索はデータ列の中央から比較を開始する方式であり，先頭から開始するのは線形探索の特徴です。
- エ誤り。2分探索の比較回数はnではなくlog₂ nに比例し，n log₂ nに比例するというのは誤りです。