整列されたn 個のデータの中から、求める要素を2分探索法で探索する。
この処理の計算量のオーダを表す式はどれか。
| ア | log n | イ | n | ウ | n2 | エ | n log n |
答え ア
【解説】
2分探索法は1回探索を行うごとに、探索する範囲を半分にしながら行っていくので、m 個のデータ配列についての探索の回数はlog2m であり、これを計算量を表すオーダにするとlog n (ア)になります。
【キーワード】
・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分探索法」について調べてみよう。
戻る
一覧へ
次へ