An algorithmic and complexity analysis of interpolation search

DOI10.1007/BF00288534zbMath0405.68057OpenAlexW1990348580MaRDI QIDQ1257344

J. Alan George, Gaston H. Gonnet, Lawrence D. Rogers

Publication date: 1980

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00288534

zbMATH Keywords

Computational ComplexityAnalysis of AlgorithmsFileInterpolation Search AlgorithmOrdered TablesVector Search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Information storage and retrieval of data (68P20) Discrete mathematics in relation to computer science (68R99) Algorithms in computer science (68W99)

Related Items (12)

Jump interpolation search trees and symmetric binary numbers ⋮ A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time ⋮ Unnamed Item ⋮ Dynamic interpolation search revisited ⋮ Fast search algorithms for look‐up tables ⋮ Batched interpolation searching on databases ⋮ Parallel processing can be harmful: The unusual behavior of interpolation search ⋮ Log-logarithmic worst-case range queries are possible in space theta(N) ⋮ Two-way chaining for non-uniform distributions ⋮ New trie data structures which support very fast search operations ⋮ Simulating interpolation search ⋮ Interpolation-binary search

Cites Work

• The interpolation-sequential search algorithm
• Understanding the complexity of interpolation search
• Notes on the derivation of asymptotic expressions from summations
• Interpolation search—a log log N search
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An algorithmic and complexity analysis of interpolation search