修了試験 2017-07-23実施分 基本情報技術者試験 問6

解説

正解は2です。 図の流れ図では、探索範囲の下端を x、上端を y として、最初に x に1、y に n を設定しています。 x が y 以下の間は、空欄 a で m を求め、k と A(m) を比較します。 k が A(m) より小さければ y を m－1 に、大きければ x を m＋1 に更新して判定に戻ります。 等しければその m のまま終了し、x が y を超えたら m を0にして終了します。 したがって、空欄 a では探索範囲の中央の位置を m に設定する必要があります。 【選択肢別解説】 1：× m に x＋y を設定すると、範囲の中央ではなく両端の和になります。 例えば x＝1、y＝n のとき m＝n＋1 となり、配列の範囲外を参照してしまいます。 2：○ m に (x＋y)／2 を設定すると、x と y の中央の位置（小数点以下切捨て）が得られます。 2分探索は中央の要素と比較して範囲を半分にする方法なので、これが正しい式です。 3：× (x－y)／2 は、x≦y の間は0以下の値になります。 添字として0や負の値を使うことになり、配列要素を正しく参照できません。 4：× (y－x)／2 は範囲の幅の半分であり、中央の位置ではありません。 例えば x＝5、y＝9 のとき m＝2 となり、探索範囲の外を参照します。 中央の位置は、これに x を加えた x＋(y－x)／2 です。 【ポイント】 2分探索では中央 m＝(x＋y)／2 の要素と比較し、小さければ上端を m－1、大きければ下端を m＋1 に更新します。 比較回数は最大でも約 log_2 n 回に抑えられます。