基本情報技術者試験の過去問と解説
[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成20年 秋期 基本情報技術者 午前 問13
問13   2分探索

 2,000 個の相異なる要素が,キーの昇順に整列された表がある。外部から入力したキーに よってこの表を2分探索して,該当するキーの要素を取り出す。該当するキーが 必ず表中にあることが分かっているとき,キーの比較回数は最大何回か。

ア 9       イ 10       ウ 11       エ 12
解答←クリックすると正解が表示されます

解説

 2分探索法は、整列されたデータの中央の値と対象データを比較し、 それより前方にあるか後方にあるかを判断する。

 前方にデータがある場合は、前半分のデータの中央のデータと比較し、 後方にデータがある場合は、後半分のデータの中央のデータと比較する。

 この操作を繰り返すことによって、検索する方法である。

 2分探索法での比較回数は、log2 n である。

 該当するキーが必ず表中にある場合、データの個数と比較回数は以下のようになる。

 データの個数   比較回数 
  3 (21+1)    1  
  5 (22+1)    2  
  9 (23+1)    3  
  17 (24+1)    4  
  33 (25+1)    5  
  65 (26+1)    6  
 129 (27+1)    7  
 257 (28+1)    8  
 513 (29+1)    9  
 1025 (210+1)    10 
 2049 (211+1)    11 
 よって、2,000 個のデータの場合、比較回数は 11 回となる。

[←前の問題] [次の問題→] [問題一覧表] [分野別] [キーワード索引] [基本情報技術者試験TOP ]