平成21年 春期 基本情報技術者 午前 問7

昇順に整列されたn 個のデータが配列に格納されている。
探索したい値を2分探索法で探索するときの、およその比較回数を求める式はどれか。

 ア  log2n  イ  (log2n +1)/2
 ウ  n  エ  n2


答え ア


解説
2分探索法は1回探索を行うごとに、探索する範囲を半分にしながら行っていくので、m 回の探索を行い探索するデータがなかったときの、データ配列の大きさは2m である。
したがって、n 個のデータ配列についての探索の回数はlog2n (ア)になる。


キーワード
・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分探索法」について調べてみよう。

戻る 一覧へ 次へ