平成18年 春期 基本情報技術者 午前 問14

昇順に整列済の配列要素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分探索法では、データ列の中央の要素のデータを比較に使用するため、aにはデータ列の中央の場所を計算する処理が入る。
探索対象のデータはx y なので、その中央の値m を求める式は(x +y )/2(イ)になる。


キーワード
・2分探索法

キーワードの解説

戻る 一覧へ 次へ