アルゴリズムとプログラミングアルゴリズムとデータ構造

ソート済みの n 個のデータに対して二分探索を行うときの、最悪計算量はどれか。

ア.O(1)

イ.O(n)

ウ.O(n log n)

エ.O(log n)正解

解説

二分探索は「毎回半分に切り捨てる」検索。1024件あっても 10回（log₂1024=10）で当たる、辞書めくりの究極形です。

なぜエが正解か

二分探索は中央要素と比較して探索範囲を毎ステップ半分にするため、最悪でも log₂n ステップで終わります。よって最悪計算量は O(log n)。電話帳を真ん中で開いて左右どちらかを捨てる、を繰り返すあの手順そのものです。

なぜアは間違いか

O(1) は「データ量に関係なく一定時間」の意味で、ハッシュ表の検索などに使われる量。比較が必要な二分探索でこの量にはなりません。

なぜイは間違いか

O(n) は線形探索（先頭から順に見る）の計算量。二分探索の利点を完全に殺してしまうので、ソート済みデータでは過剰見積もりです。

なぜウは間違いか

O(n log n) はソート系アルゴリズムの典型量。検索1回ではなく「全要素をソートする」場面で出てくる量なので、用途を取り違えた選択肢です。

出典: AI生成問題（学習用）

← 前の問題

n 個のデータをソートするとき、最悪計算量が O(n²) となるソートアルゴリズムはどれか。

次の問題 →

空のスタックに対して、push(1)、push(2)、push(3)、pop、push(4)、pop、pop の操作を順に行ったとき、最後に pop で取り出される値はどれか。