昇順に整列済みの配列要素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分探索法
- 2分探索法
整列されたデータ内から、目的のデータを探す方法。
「整列された」とは大きい順(降順)や、小さい順(昇順)にデータが並んでいる状態になっていること。
2分探索法について例を示しながら説明する。探す対象となるデータが1…Nの順で昇順の場合、まず(1+N)/2番目のデータと目的のデータの大小を比較する。
(1+N)/2番目のデータが探しているデータの場合、
探索終了。
(1+N)/2番目のデータが探しているデータより小さい場合、
1…((1+N)/2-1)のデータに対し同様の探索を行う。
(1+N)/2番目のデータが探しているデータより大きい場合、
((1+N)/2+1)…Nのデータに対し同様の探索を行う。
もっと、「2分探索法」について調べてみよう。
戻る
一覧へ
次へ