Interpolation search—a log log N search
- 1 July 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 21 (7), 550-553
- https://doi.org/10.1145/359545.359557
Abstract
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 log N 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.Keywords
This publication has 5 references indexed in Scilit:
- Understanding the complexity of interpolation searchInformation Processing Letters, 1977
- The complexity of searching an ordered random tablePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- ELEMENTS OF STOCHASTIC PROCESSESPublished by Elsevier BV ,1975
- File Organization: On the Selection of Random Access Index Points for Sequential FilesJournal of the ACM, 1969
- Addressing for Random-Access StorageIBM Journal of Research and Development, 1957