応用情報技術者 予想問題｜練習問題 第17問

解説

二分探索（バイナリサーチ）はソート済み配列を毎回半分に絞り込むため、最悪・平均ともに O(log n) で完了する。1024 要素なら高々 10 回、100 万要素でも 20 回程度で済む。前提としてソート済みであることが必要で、未整列の場合は線形探索 O(n) しか使えない。挿入の多いデータには平衡木（赤黒木、AVL）や B 木が向く。STL の lower_bound や JDK の Arrays.binarySearch、Python の bisect が標準実装として提供されている。