| 基本情報技術者試験 |
2012年度 ＝ 平成24年度・秋期 |
午前 |
問6 |
昇順に整列済みの配列要素A(1)、A(2)、…、A(n )から、A(m )＝k となる配列要素A(m )の添字m を２分探索法によって見つける処理を図に示す。終了時点でm ＝0である場合は、A(m )＝k となる要素は存在しない。図中のａに入る式はどれか。ここで、“／”は、小数点以下を切り捨てる除算を表す。
| ア (x ＋y ) → m
| イ (x ＋y )／2 → m
|
| ウ (x －y )／2 → m
| エ (y －x )／2 → m
|
イ
２分探索法は、整列済みの配列の中央に位置する要素と等しいか／大きいか／小さいかの判断を行い、探索すべき範囲を半分ずつに絞り込んでいく探索法です。
たとえば、以下の配列a[1]～a[7]から3を探索する場合を考えましょう。
a[1] 2 ■■
a[2] 3 ■■■
a[3] 5 ■■■■■
a[4] 6 ■■■■■■
a[5] 8 ■■■■■■■■
a[6] 8 ■■■■■■■■
a[7] 9 ■■■■■■■■■
中央に位置するa[4]の値は6ですから、探索すべき範囲はa[1]～a[3]に絞られます（もし探索すべき値が6であれば、この時点で探索は終了です）。このように、中央値との比較を行って探索すべき範囲を半分に絞っていき、その値が見つかって探索に成功するか、あるいは探索すべき範囲がなくなって探索に失敗するまで繰り返します。
フローチャートの空欄ａに入るのは、探索すべき範囲の中央要素の添字m を求める式です。たとえば上の例であればx が1でy が7ですから、m の値4を求めなければなりません。したがって、正解は(x ＋y )／2 → m です。
