修了試験 2011-07-24実施分 基本情報技術者試験 問7

解説

正解は2です。 2分探索法が正しく働くための前提条件を問う問題です。 2分探索法は、探索範囲の中央の値と目的の値を比べ、範囲を半分ずつに絞り込む方法です。 【選択肢別解説】 1：× 降順に並んでいる場合も、大小比較の向きを逆にすれば同じように探索できます。 昇順に限る必要はありません。 2：○ 中央の値との比較で、目的の値が前半か後半かを判断するには、データが整列済みである必要があります。 昇順でも降順でも整列していれば正しく探索できます。 3：× 整列していないデータでは、2分探索法はそもそも正しい結果を返せません。 「効率よく」という効率の差ではなく、正しく探索できるかどうかの問題です。 4：× データの個数が偶数か奇数かは関係ありません。 中央の位置を切り捨てなどで決めれば、どちらでも探索できます。 【ポイント】 2分探索法の比較回数は、データ数をnとするとおおむねlog2 n回です。 ただし、データがあらかじめ整列されていることが前提条件です。