二分探索木の時間計算量 (平均O(log n), 最悪O(n))

**二分探索木の時間計算量 (平均O(log n), 最悪O(n))**は、探索範囲を中央の比較で半分ずつ捨てる探索法である。

仕組み

整列済み列で中央値と目的値を比較し、小さければ左半分、大きければ右半分へ境界を更新する。

計算量・性質

反復回数は高々⌈log2(n+1)⌉程度で時間O(log n)、反復実装の補助領域O(1)。

具体例

[2,5,8,12,16]から12を探すと8より右、次の12で発見する。

限界と注意点

未整列データには使えず、境界更新と中央計算のoff-by-oneに注意する。