Technical Report CS0085

Title: Interpolation Search - a Log Log N Search
Authors: Yehoshua Perl, Alon Itai and Haim Avni
Abstract: Interpolation search is a method of retrieving a desired record by key in an ordered file, using the value of the key and the statistical distribution of the keys. It is shown that log log N file accesses on the average 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.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1976
To the main CS technical reports page

Computer science department, Technion