二分探索木における先行者 (Predecessor) と後継者 (Successor) の検索

二分探索木における先行者 (Predecessor) と後継者 (Successor) の検索は、探索範囲を中央の比較で半分ずつ捨てる探索法である。

仕組み

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

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

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

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