テクノロジ系
秋期
基本情報技術者 2012年 秋期 問6
6 / 80
昇順に列済みの配列要素A(1),A(2),・・,A(2)から、A(m)=んとなる配列要素 A(m)の添字mを2分探索法によって見つける処理を図に示す。終了時点でm=0で ある場合は、A(m)=んとなる要素は存在しない。図中のaに入る式はどれか。ここで、 "/”は、小数点以下を切り捨てる除算を表す。 開始 1→8 n→y > u 0→ m = k:A(m) 終了 m2-1→y m+1→x
正解と解説
表示する
正解 イ
(x+y) /2→m
2分探索では探索範囲の中央の添字を求めます。範囲の下限x・上限yの中央は(x+y)/2(小数切り捨て)なので、これをmに代入する式が図中aに入ります。