第２種情報処理技術者試験
1998年度 ＝ 平成10年度・春期
午前
問16
２分探索法に関する次の記述のうちで、適切なものはどれか。
ア
データが昇順に並んでいるときだけ正しく探索できる。
イ
データが昇順又は降順に並んでいるときだけ正しく探索できる。
ウ
データが昇順又は降順に並んでいる方が効率よく探索できる。
エ
データの個数が偶数のときだけ正しく探索できる。
解答
イ
解説
２分探索法は、整列済みの配列の中央に位置する要素と等しいか／大きいか／小さいかの判断を行い、探索すべき範囲を半分ずつに絞り込んでいく探索法です。
たとえば、以下の配列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であれば、この時点で探索は終了です）。このように、中央値との比較を行って探索すべき範囲を半分に絞っていき、その値が見つかって探索に成功するか、あるいは探索すべき範囲がなくなって探索に失敗するまで繰り返します。
ここでは、
データが昇順に並んでいる例を示しましたが、もちろん降順に並んでいる場合も同様に探索を行うことができます
。
