Given a set S of N distinct elements in random order and a pivot x is an element of S, we study the problem of simultaneously finding the left and the right neighbors of x, i.e., L = max u|u < x and R = min(v|v > x). We analyze an adaptive algorithm that solves this problem by scanning the set S while maintaining current values for the neighbors L and R. Each new element inspected is compared first against the neighbor in the most populous side, then (if necessary) against the neighbor in the other side, and finally (if necessary), against the pivot. This algorithm may require 3N comparisons in the worst case, but it performs well on the average. If the pivot has rank αN, where α is fixed and <0.5, the algorithm does (1 + α)N + Θ(log N) comparisons on the average, with a variance of 3lnN + Θ(1). However, in the case where the pivot is the median, the average becomes 3/2N + Θ(√(N)), while the variance grows to (0.5 − π/8)N + Θ(log N). We also prove that, in the αN case, the limit distribution is Gaussian.
