平成27年 春期 基本情報技術者 午前 問6

整列された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のデータに対し同様の探索を行う。

戻る 一覧へ 次へ