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

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

平成24年度秋季問題

問題6

昇順に整列済みの配列要素 A(1), A(2), …, A(n) から,A(m)=k となる配列要素 A(m) の添字 m を2分探索法によって見つける処理を図に示す。終了時点で m=0 である場合は,A(m)=k となる要素は存在しない。図中の a に入る式はどれか。ここで「/」は,小数点以下を切り捨てる除算を表す。

ア (x+y)→m
イ (x+y)/2→m
ウ (x-y)/2→m
エ (y-x)/2→m

昇順に整列済みの配列要素 A(1), A(2), …, A(n) から,A(m)=k となる配列要素 A(m) の添字 m を2分探索法によって見つける処理を図に示す。終了時点で m=0 である場合は,A(m)=k となる要素は存在しない。図中の a に入る式はどれか。ここで「/」は,小数点以下を切り捨てる除算を表す。

ア (x+y)→m
イ (x+y)/2→m
ウ (x-y)/2→m
エ (y-x)/2→m

解答：イ

＜解説＞

2分探索法は，整列済みの配列から効率よくデータを探索するための方法である。

2分探索法は、整列されたデータの中央の値と対象データを比較し、それより前方にあるか後方にあるかを判断する。
前方にデータがある場合は、前半分のデータの中央のデータと比較し、後方にデータがある場合は、後半分のデータの中央のデータと比較する。
この操作を繰り返すことによって、検索する方法である。

「2分探索法は、整列されたデータの中央の値と対象データを比較」なので、2で割って中央値を求めます。

したがって、イ)(x+y)/2→mが正解である。