平成24年 秋期 基本情報技術者 午前 問6

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

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


答え イ


解説
2分探索法では下図のような整列された配列から、データを探す方法であり、
 
まず、配列の先頭をx 、最後をy として
 
その真ん中の要素を指すm を求める。
 
したがって、m を求める式は(x + y )/2→m (イ)になる。


キーワード
・2分探索法

キーワードの解説

戻る 一覧へ 次へ