[0280] 2分探索

平成11年度秋期 (旧)第2情報処理技術者試験より
2分探索において、整列されているデータの個数が 4倍になると、最大探索回数はどうなるか。
1回増える。
2回増える。
約2倍になる。
約4倍になる。

正解

解説

 2分探索に関する問題です。

 2分探索とは、探索アルゴリズムのひとつで、バイナリサーチとも呼ばれます。あらかじめソートされたデータ要素の中央に位置するデータを比較し、その大小関係によって探索範囲を狭めていく方法です。線形探索(バックナンバー0140号参照)と比べて、やや複雑なアルゴリズムになりますが、計算回数が少ないので、すばやく目的のデータにたどり着ける特長を持っています。




 問題文では、データ要素数が 4倍になったときに、最大探索回数がどうなるかを求めています。上図での説明のように、2分探索では 1回の探索ごとに、探索範囲がおよそ半分になります。したがって、データ要素数が 4倍になっても、1回目の探索完了で、未探索範囲が元のデータ要素数の約 2倍、2回目の完了で元のデータ要素数とほぼ同じになります。



 よって、探索回数が 2回増加するので、イが正解となります。
※ 解説の内容は執筆時点のものであり,含まれている情報の正確性,妥当性について保証するものではありません。ご注意ください・・・

関連する(かもしれない)問題