Interpolation search—a log log N search
From MaRDI portal
Publication:4157947
DOI10.1145/359545.359557zbMath0378.68029OpenAlexW2022541337WikidataQ56039264 ScholiaQ56039264MaRDI QIDQ4157947
Yehoshua Perl, Alon Itai, Haim Avni
Publication date: 1978
Published in: Communications of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/359545.359557
Analysis of algorithms and problem complexity (68Q25) Information storage and retrieval of data (68P20) General topics in the theory of software (68N01) Algorithms in computer science (68W99)
Related Items
Jump interpolation search trees and symmetric binary numbers, Operations research applications of dichotomous search, Controlled density sorting, Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines, Expected complexity of fast search with uniformly distributed data, Improved bounds for finger search on a RAM, A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time, Unnamed Item, Analysis of recursive batched interpolation search, Understanding the complexity of interpolation search, Dynamic interpolation search revisited, An algorithmic and complexity analysis of interpolation search, Voronoi diagrams with barriers and on polyhedra for minimal path planning, An adaptation of a root finding method to searching ordered disk files revisited, 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), New trie data structures which support very fast search operations, Simulating interpolation search, Interpolation-binary search