Understanding the complexity of interpolation search
From MaRDI portal
Publication:1245570
DOI10.1016/0020-0190(77)90072-2zbMath0376.68038WikidataQ56050587 ScholiaQ56050587MaRDI QIDQ1245570
Edward M. Reingold, Yehoshua Perl
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
Related Items
Dynamic-window search for real-time simulation of dynamic systems, Fast search algorithms for look‐up tables, New trie data structures which support very fast search operations, Interpolation-binary search, Jump interpolation search trees and symmetric binary numbers, Expected complexity of fast search with uniformly distributed data, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, On a generalization of binary search, An algorithmic and complexity analysis of interpolation search, Simulating interpolation search, Parallel processing can be harmful: The unusual behavior of interpolation search, Log-logarithmic worst-case range queries are possible in space theta(N), Optimal bounds for the predecessor problem and related problems, Improved bounds for finger search on a RAM
Cites Work