Interpolation Search—A Log LogN Search

Yehoshua Perl; Alon Itai; Haim Avni

doi:10.1145/359545.359557

Interpolation Search—A Log LogN Search

Yehoshua Perl, Alon Itai, Haim Avni

Research output: Contribution to journal › Article › peer-review

91 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 language	English (US)
Pages (from-to)	550-553
Number of pages	4
Journal	Communications of the ACM
Volume	21
Issue number	7
DOIs	https://doi.org/10.1145/359545.359557
State	Published - Jul 1 1978
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science

Keywords

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

Access to Document

10.1145/359545.359557

Cite this

@article{5471e15bf17c4638b605b420e63fc98f,

title = "Interpolation Search—A Log LogN Search",

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

keywords = "average number of accesses, binary search, database, interpolation search, retrieval, searching, uniform distribution",

author = "Yehoshua Perl and Alon Itai and Haim Avni",

year = "1978",

month = jul,

day = "1",

doi = "10.1145/359545.359557",

language = "English (US)",

volume = "21",

pages = "550--553",

journal = "Communications of the ACM",

issn = "0001-0782",

publisher = "Association for Computing Machinery (ACM)",

number = "7",

}

TY - JOUR

T1 - Interpolation Search—A Log LogN Search

AU - Perl, Yehoshua

AU - Itai, Alon

AU - Avni, Haim

PY - 1978/7/1

Y1 - 1978/7/1

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

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

KW - average number of accesses

KW - binary search

KW - database

KW - interpolation search

KW - retrieval

KW - searching

KW - uniform distribution

UR - http://www.scopus.com/inward/record.url?scp=0017995344&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0017995344&partnerID=8YFLogxK

U2 - 10.1145/359545.359557

DO - 10.1145/359545.359557

M3 - Article

AN - SCOPUS:0017995344

SN - 0001-0782

VL - 21

SP - 550

EP - 553

JO - Communications of the ACM

JF - Communications of the ACM

IS - 7

ER -

Interpolation Search—A Log LogN Search

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this