Understanding the complexity of interpolation search

DOI10.1016/0020-0190(77)90072-2zbMath0376.68038OpenAlexW2060978005WikidataQ56050587 ScholiaQ56050587MaRDI QIDQ1245570

Yehoshua Perl, Edward M. Reingold

Publication date: 1977

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(77)90072-2

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Related Items (16)

Jump interpolation search trees and symmetric binary numbers ⋮ Expected complexity of fast search with uniformly distributed data ⋮ Improved bounds for finger search on a RAM ⋮ Dynamic interpolation search in o(log log n) time ⋮ A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time ⋮ Dynamic interpolation search revisited ⋮ On a generalization of binary search ⋮ An algorithmic and complexity analysis of interpolation search ⋮ Dynamic-window search for real-time simulation of dynamic systems ⋮ Fast search algorithms for look‐up tables ⋮ Parallel processing can be harmful: The unusual behavior of interpolation search ⋮ Log-logarithmic worst-case range queries are possible in space theta(N) ⋮ New trie data structures which support very fast search operations ⋮ Simulating interpolation search ⋮ Interpolation-binary search ⋮ Optimal bounds for the predecessor problem and related problems

Cites Work

• Interpolation search—a log log N search
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Understanding the complexity of interpolation search