二分探索を用いて、昇順にソート済みの n 個の要素から目的の値を探すときの最悪時間計算量はどれですか？

二分探索は、探索範囲の中央の要素と目的の値を比べ、範囲を毎回半分に絞り込んでいく手法です。要素数 n が 1 になるまでに必要な分割回数は約 log2(n) 回なので、最悪時間計算量は O(log n) になります。たとえば 100 万件でも約 20 回の比較で見つかります。ただし、データがあらかじめソートされていることが前提条件です。ソートされていない場合は先頭から順に調べる線形探索になり、計算量は O(n) です。