Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
Dan E. Willard · SIAM Journal on Computing · 1985
The first algorithm that searches unindexed and nonuniformly distributed ordered files in $\log \log N$ expected time is presented in this paper. Our analysis rests on a synthesis of concepts from the literature on interpolation search and on the method of regula falsi in numerical analysis.