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