Interpolation Search -A Log LogN Search

Interpolation search is a method of retrieving
a desired record by key in an ordered file by 
using the value of the key and the statistical distribution
of the keys.  It is shown that on the average 
log logN file accesses are required to retrieve a key,
assuming that the N keys are uniformly distributed. 
 The number of extra accesses is also estimated and shown
to be very low.  The same holds if the cumulative 
distribution function of the keys is known.  Computational
experiments confirm these results.  

CACM July, 1978

Perl, Y.
Itai, A.
Avni, H.

Average number of accesses, binary search, database,
interpolation search, retrieval, searching, 
uniform distribution 

4.4 4.6 5.25

CA780704 DH February 7, 1979  4:50 PM

3084	5	3084
3084	5	3084
3084	5	3084