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

顧客番号をキーとして顧客データを検索する場合、2分探索を使用するのが適しているものはどれか。

 ア  顧客番号から求めたハッシュ値が指し示す位置に配置されているデータ構造
 イ  顧客番号に関係なく、ランダムに配置されているデータ構造
 ウ  顧客番号の昇順に配置されているデータ構造
 エ  顧客番号をセルの格納し、セルのアドレス順に配置されているデータ構造


答え ウ


解説
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のデータに対し同様の探索を行う。

もっと、「2分探索法」について調べてみよう。

戻る 一覧へ 次へ