修了試験 2018-12-09実施分 基本情報技術者試験 問6

解説

正解は1です。 2分探索（バイナリサーチ）の前提条件と性質を問う問題です。 2分探索は、探索範囲の中央の値と探す値を比べ、範囲を半分ずつに絞り込んでいく方法です。 【選択肢別解説】 1：○ 中央の値との大小比較で、探す値が前半と後半のどちらにあるかを判断します。 そのため、データ列が昇順または降順に整列されている必要があります。 2：× 探す値が先頭付近にある場合などは、線形探索のほうが少ない比較回数で見つかることがあります。 「常に速く探索できる」という記述は誤りです。 3：× データ列の先頭から順に探索するのは線形探索です。 2分探索は、データ列の中央から比較を始めます。 4：× 2分探索の比較回数は、最大でもおよそlog_2 n回です。 n log_2 nではなく、log_2 nに比例します。 【ポイント】 平均比較回数は、線形探索がおよそn/2回、2分探索がlog_2 nに比例する回数です。 n log_2 nはクイックソートなど高速な整列アルゴリズムの平均計算量なので、混同しないようにしましょう。