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.

REFERENCES

• 1: Doob, J.L. Stochastic Processes, Wiley, New York, 1967.
• 2: Feller, W. An Introduction to Probability Theory and Its Applications, Vol. 1. Wiley, New York, third ed., 1968.
• 3: S. P. Ghosh , M. E. Senko, File Organization: On the Selection of Random Access Index Points for Sequential Files, Journal of the ACM (JACM), v.16 n.4, p.569-579, Oct. 1969 [doi>10.1145/321541.321546]
• 4: Karlin, S., and Taylor, H.M. A First Course in Stochastic Processes. Academic Press, New York, second ed., 1975.
• 5: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 6: Perl, Y., and Reingold, E.M. Understanding and complexity of interpolation Search. Infrm. Proc. Letters, 6 (1977), 219-222.
• 7: Peterson, W.W. Addressing for random-access storage. IBM J. Res. and Develop. 1 (1957), 131-132.
• 8: Yao, A.C., and Yao, F.F. The complexity of searching an ordered random table. Proc. Seventeenth Annual Symp. Foundations ofComptr. Sci., 1976, pp. 173-177.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Interpolation formulas

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Design, Management, Performance, Theory

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