We present a new finger search tree with O( log log d) expected search time in the Random Access Machine (RAM) model of computation for a large class of input distributions. The parameter d represents the number of elements (distance) be- tween the search element and an element pointed to by a finger, in a finger search tree that stores n elements. Our data structure improves upon a previous result by Andersson and Mattsson that exhibits expected O( log log n) search time by incorporating the distance d into the search time complexity, and thus removing the dependence on n . We are also able to show that the search time is O( log log d + φ(n)) with high prob- ability, where φ(n) is any slowly growing function of n . For the need of the analysis we model the updates by a “balls and bins” combinatorial game that is interesting in its own right as it involves insertions and deletions of balls according to an unknown distribution.