ITパスポート 予想問題｜練習問題 第85問

解説

二分探索は、整列済みのデータに対して中央の要素と目的の値を比較し、探索範囲を半分に絞る操作を繰り返すアルゴリズムである。n個のデータでも1回の比較ごとに範囲が半減するため、比較回数はおよそlog2(n)回で済み、計算量はO(log n)となる。よってイが正解である。例えばn＝1,000なら約10回、n＝100万でも約20回の比較で探索できる。アのO(1)は配列の添字アクセスのように一定時間で済む処理、ウのO(n)は先頭から順に調べる線形探索、エのO(n^2)はバブルソートなど二重ループの処理の計算量である。「二分探索は整列済みが前提」という条件と、線形探索O(n)との対比が頻出ポイントである。