ITの基礎知識|ITパスポート・基本情報

基本情報技術者 平成19年秋 問14

2017.10.05

昇順に整列された n 個のデータが格納されている配列 A がある。流れ図は, 2分探索法を用いて配列 A からデータ x を探し出す処理を表している。 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  

 

Show answer

正解: ウ

解説:

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

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

a,bの直前でA(k) と x を比較しているが、それによって「等しいければxは存在する」「A(k) は x より小さいので、xはそれより後にある」「A(k) は x より大きいので、xはそれより前にある」のいずれかが分かる。

これを踏まえて空欄を埋める。

A(k) の方が小さいときは、xはそれより後にあるので、次は後ろ半分を探すことになる。よって、k+1 を lo に入れれば、A(k) の次の要素を先頭にした後ろ半分が次の検索範囲となる。

逆に A(k) の方が大きいときは、xはそれより手前にあるので、次は前半分を探すことになる。よって、k-1 を hi に入れれば、A(k) の手前の要素を末尾にした前半分が次の検索範囲となる。