平成27年度 春期 基本情報技術者試験 午前 問6

解説

2分探索法は，整列済みのデータに対して探索範囲を毎回半分に絞り込んでいく探索方法です。n個のデータに対して比較を繰り返すたびに探索範囲がおよそ半分になるため，最悪の場合でも比較回数はlog₂nのオーダになります。線形探索のオーダnや，nlog nのオーダのソートアルゴリズムとは計算量の桁が異なります。

選択肢ごとの解説

• ア正しい。2分探索法は探索範囲を毎回半分にしていくため，計算量のオーダはlog nになります。
• イ誤り。オーダnは，先頭から順に調べる線形探索の計算量です。2分探索法はこれより高速です。
• ウ誤り。オーダn²は，単純な選択ソートやバブルソートなど，2重ループを伴う処理の計算量です。
• エ誤り。オーダn log nは，クイックソートやマージソートなど，多くの高速な整列アルゴリズムの計算量です。