昇順に整列済の配列要素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分探索法
- 2分探索法
整列(ソート)済みのデータ列に対して行う探索方法で、データ列の中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、探索範囲を狭めながら行っていく方法です。
もっと、「2分探索法」について調べてみよう。
戻る
一覧へ
次へ