O(log n)アルゴリズムの例 (二分探索、平衡二分探索木の操作)
**O(log n)アルゴリズムの例 (二分探索、平衡二分探索木の操作)**は、探索範囲を中央の比較で半分ずつ捨てる探索法である。
仕組み
整列済み列で中央値と目的値を比較し、小さければ左半分、大きければ右半分へ境界を更新する。
計算量・性質
反復回数は高々⌈log2(n+1)⌉程度で時間O(log n)、反復実装の補助領域O(1)。
具体例
[2,5,8,12,16]から12を探すと8より右、次の12で発見する。
限界と注意点
未整列データには使えず、境界更新と中央計算のoff-by-oneに注意する。