基本情報技術者試験 基本情報技術者試験 平成26年度 秋期 午前 午前 問6: 2分探索に関する記述のうち，適切なものはどれか。

問題本文

2分探索に関する記述のうち，適切なものはどれか。

選択肢

• ア.2分探索するデータ列は整列されている必要がある。
• イ.2分探索は線形探索よりも常に速く探索できる。
• ウ.2分探索は探索をデータ列の先頭から開始する。
• エ.n個のデータの2分探索に要する比較回数は， に比例する。

正解

ア. 2分探索するデータ列は整列されている必要がある。

解説

2分探索は中央要素と比較して半分に絞り込む手法のため、データが整列されていることが前提条件です。比較回数は に比例します。

選択肢ごとの解説

• ア.ソート済みデータでないと中央比較で範囲を絞れないため、整列が前提条件です。
• イ.n が小さいときや探索値が先頭付近のときは線形探索の方が速いケースもあります。
• ウ.2分探索は中央から始めるアルゴリズムで、先頭からではありません。
• エ.比較回数は に比例し、 ではありません。