平成24年度 秋期 基本情報技術者試験 午前 問6
テクノロジ／アルゴリズム昇順に整列済みの配列要素A(1)，A(2)，…，A(n)から，A(m)＝kとなる配列要素A(m)の添字mを2分探索法によって見つける処理を図に示す。終了時点でm＝0である場合は，A(m)＝kとなる要素は存在しない。図中のaに入れる式はどれか。ここで，“／”は，小数点以下を切り捨てる除算を表す。
出典：平成24年度 秋期 基本情報技術者試験 午前 問6
- ア(x＋y)→m
- イ(x＋y)／2→m
- ウ(x－y)／2→m
- エ(y－x)／2→m
正解：イ
解説
2分探索では，探索範囲の下限xと上限yの中央付近の添字mを求め，A(m)とkを比較して範囲を絞り込みます。図の流れでは，aの処理で中央の添字mを計算してから，k：A(m)の比較を行っています。中央値の計算式は(x＋y)を2で割って小数点以下を切り捨てる(x＋y)／2→mです。
選択肢ごとの解説
- ア誤り。2で割る処理がなく，mがxとyの和のままになってしまい，配列の範囲を超えた添字になり得ます。
- イ正しい。x行とy行の中央の添字を求めるには，(x＋y)を2で割った(x＋y)／2をmに代入します。
- ウ誤り。(x－y)は範囲の幅の負の値であり，中央の添字を正しく求められません。
- エ誤り。(y－x)は範囲の幅ですが，これを2で割った値だけではxを起点とした中央の添字になりません。