| 第２種情報処理技術者試験 |
1999年度 ＝ 平成11年度・春期 |
午前 |
問29 |
昇順に整列されたn個のデータが格納されている配列Aがある。流れ図は、配列Aからデータxを2分探索法を用いて探し出す処理である。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
|
ウ
２分探索法は、整列済みの配列の中央に位置する要素と等しいか／大きいか／小さいかの判断を行い、探索すべき範囲を半分ずつに絞り込んでいく探索法です。
たとえば、以下の配列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であれば、この時点で探索は終了です）。このように、中央値との比較を行って探索すべき範囲を半分に絞っていき、その値が見つかって探索に成功するか、あるいは探索すべき範囲がなくなって探索に失敗するまで繰り返します。
したがって、ａはk＋1 → lo、ｂはk－1 → hiとなります。
