修了試験 2020-12-13実施分 基本情報技術者試験 問10

解説

正解は3です。 2分探索は、探索範囲の中央の値と目的の値を比べ、範囲を半分ずつ絞り込む探索法です。 この方法が使えるのは、データがキーの順に整列（ソート）されている場合に限られます。 n件のデータでも、比較回数はおよそlog₂n回で済みます。 【選択肢別解説】 1：× ハッシュ値が指す位置にデータを置く構造には、ハッシュ表探索が適しています。 キーの順に並んでいないので、2分探索は使えません。 2：× ランダムに配置されたデータは、大小関係で範囲を半分に絞れません。 先頭から順に調べる線形探索を使うことになります。 3：○ 顧客番号の昇順に並んでいるので、中央の値との比較で探索範囲を半分ずつ狭められます。 2分探索の前提を満たしています。 4：× セルのアドレス順に並んでいても、顧客番号の大小順に並んでいるとは限りません。 キーで整列していなければ2分探索は使えません。 【ポイント】 2分探索の前提条件は「キーで整列済み」であることです。 線形探索は整列不要、ハッシュ表探索はハッシュ関数による配置が前提、と探索法ごとの前提を区別しておきましょう。