Interpolation Search—A Log LogN Search

Yehoshua Perl, Alon Itai, Haim Avni

Research output: Contribution to journalArticlepeer-review

76 Scopus citations

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 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.

Original languageEnglish (US)
Pages (from-to)550-553
Number of pages4
JournalCommunications of the ACM
Volume21
Issue number7
DOIs
StatePublished - Jul 1 1978
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • average number of accesses
  • binary search
  • database
  • interpolation search
  • retrieval
  • searching
  • uniform distribution

Fingerprint

Dive into the research topics of 'Interpolation Search—A Log LogN Search'. Together they form a unique fingerprint.

Cite this