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

平成19年 秋期 基本情報技術者 午前 問14
問14   2分探索法

 昇順に整列された n 個のデータが格納されている配列 A がある。流れ図は, 2分探索法を用いて配列 A からデータ x を探し出す処理を表している。 a, b に入る操作の正しい組合せはどれか。ここで,除算の結果は小数点以下が切り捨てられる。

      a     b   
  ア   k+1→ hi    k-1→ lo  
  イ   k-1→ hi    k+1→ lo  
  ウ   k+1→ lo    k-1→ hi  
  エ   k-1→ lo    k+1→ hi  

解答←クリックすると正解が表示されます

解説

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

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

 A(k) と x を比較し、A(k) の方が小さいときは、k+1 を lo に入れる。 A(k) の方が大きいときは、k-1 を hi に入れる。

【平成11年春 問29】


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