問題プレビューID: f5ee0371基本情報技術者試験 午前免除試験 2011年1月

問 8
基本情報技術者試験 午前免除試験 2011年1月

昇順に整列された nn 個のデータが格納されている配列 AA がある。流れ図は,2 分探索法を用いて配列 AA からデータ xx を探し出す処理を表している。a,b に入る操作の正しい組合せはどれか。ここで,除算の結果は小数点以下が切り捨てられる。

ab
アk+1→hik+1 \to hik−1→lok-1 \to lo
イk−1→hik-1 \to hik+1→lok+1 \to lo
ウk+1→lok+1 \to lok−1→hik-1 \to hi
エk−1→lok-1 \to lok+1→hik+1 \to hi
解説

正解は「ウ」です。

配列 AA は昇順に整列されているので,中央の要素 A(k)A(k) と探索する値 xx を比較することで,探索範囲を半分に絞り込めます。

  • A(k)<xA(k) < x のとき(流れ図の「<」の枝):xx は A(k)A(k) より大きいので,求める値は中央より後ろ(添字の大きい側)にあります。そこで探索範囲の下限を中央の次に移し,lo←k+1lo \leftarrow k+1 とします。これが a です。
  • A(k)>xA(k) > x のとき(流れ図の「>」の枝):xx は A(k)A(k) より小さいので,求める値は中央より前(添字の小さい側)にあります。そこで探索範囲の上限を中央の前に移し,hi←k−1hi \leftarrow k-1 とします。これが b です。

したがって,a=k+1→lok+1 \to lo,b=k−1→hik-1 \to hi となり,「ウ」が正解です。

  • ア・イ・エ: いずれも探索範囲の更新方向が逆,又は lo と hi の対応を取り違えた組合せであり,正しくありません。

関連問題

本文が同じ・似ている問題を表示しています