Predecessor search with distance-sensitive query time

Djamal Belazzougui, Paolo Boldi, Sebastiano Vigna

A predecessor (successor) search finds the largest element $x^{-}$ smaller than the input string $x$ (the smallest element $x^{+}$ larger than or equal to $x$, respectively) out of a g…