修了試験 2017-07-23実施分 基本情報技術者試験 問6
昇順に整列済みの配列要素A(1),A(2),…,A(n)から,A(m)=kとなる配列要素A(m)の添字mを2分探索法によって見つける処理を図に示す。 終了時点でm=0である場合は,A(m)=kとなる要素は存在しない。 図中のaに入る式はどれか。 ここで,"/"は,小数点以下を切り捨てる除算を表す。

正答2
解説
正解はイ。 2分探索では探索範囲[x,y]の中央の添字を求めるため,aには(x+y)/2→mが入る。 求めたA(m)とkを比較し,大小関係に応じてxまたはyを更新して探索範囲を半分に絞り込んでいく。まとめて解く
修了試験 2017-07-23実施分を通しで解く(80問)→