  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 given set $S$; in this paper, we consider the static
case (i.e., $S$ is fixed and does not change over time) and assume that the $n$
elements of $S$ are available for inspection. We present a number of algorithms
that, with a small additional index (usually of O(n log w) bits, where $w$ is
the string length), can answer predecessor/successor queries quickly and with
time bounds that depend on different kinds of distance, improving significantly
several results that appeared in the recent literature. Intuitively, our first
result has a running time that depends on the distance between $x$ and $x^\pm$:
it is especially efficient when the input $x$ is either very close to or very
far from $x^-$ or $x^+$; our second result depends on some global notion of
distance in the set $S$, and is fast when the elements of $S$ are more or less
equally spaced in the universe; finally, for our third result we rely on a
finger (i.e., an element of $S$) to improve upon the first one; its running
time depends on the distance between the input and the finger.
