昇順に整列済みの配列要素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分探索法