二分探索の計算量はどれか？

📝 解説

二分探索（バイナリサーチ）は「整列済みデータの中央値と比較して探索範囲を半分に絞る」を繰り返す高速探索アルゴリズムです。辞書で単語を調べるとき、まず真ん中のページを開いて「目的の単語は前か後か」で半分に絞り込む方法と全く同じです。毎回データが半分になるため、n件のデータを探すのに必要な最大比較回数はlog₂n回です。1000件なら約10回、100万件でも約20回で見つかります！これがO(log n)の威力です。前提として「データが昇順または降順にソートされていること」が必須です。誤答のO(n)は線形探索（先頭から順番に調べる）の計算量で、整列不要ですが遅い。O(n²)はバブルソートなど単純ソートの計算量、O(n log n)はクイックソートなど高速ソートの計算量です。「二分探索＝O(log n)＝ソート済みが前提」をしっかり覚えて、他の計算量との混同を避けましょう！