必ず受かる情報処理技術者試験

当サイトは、情報処理技術者試験に合格するためのWebサイトです。
ITパスポート試験，基本情報技術者,応用情報技術者,高度試験の過去問題と解答及び詳細な解説を掲載しています。
  1. トップページ
  2. 基本情報技術者
  3. 平成19年度秋季問題一覧
  4. 平成19年度秋季問題14-解答・解説-分析

平成19年度秋季問題

問題14

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

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

解答：ウ

＜解説＞

2分探索法では，探索範囲を右半分または左半分に縮小して，再びその中央のデータとの比較を繰り返すことで探索を行う。
昇順にソートされたデータ列の場合、探索範囲の中央のデータA（k ）と対象データxとを比較し、

  • A（k ）＝x のときは，探索を終了する。
  • A（k ）＜x であれば，対象データx は中央より右半分を探索すればよい。
    すなわち、空欄aはk ＋1→lo が適切。
  • A （k ）＞x であれば対象データxは中央より左半分を探索すればよい。
    すなわち、空欄bはk －1→hi が適切。

よってウが正解である。