平成18年 秋期 基本情報技術者 午前 問14

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

【キーワード】
・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のデータに対し同様の探索を行う。
• 比較回数
  コンピュータに行わせる多くの作業は、『データを探す(探索)』や『データを並び替える(整列、ソート)』で、これらの作業で最も時間のかかる処理は一般的に比較処理と考えられているため、比較回数の少ない方法(アルゴリズム)を用いることが時間の処理作業時間の短縮になると考えられている。
  『データを探す』や『データを並び替える』の作業では使用する方法(アルゴリズム)によって比較回数がデータの母数(n)を使った式で表すことができこれをオーダ(O ( ))と呼ぶ。

戻る 一覧へ 次へ