Interpolation search—a log log N search
From MaRDI portal
Publication:4157947
DOI10.1145/359545.359557zbMath0378.68029WikidataQ56039264 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
68Q25: Analysis of algorithms and problem complexity
68P20: Information storage and retrieval of data
68N01: General topics in the theory of software
68W99: Algorithms in computer science
Related Items
Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines, Analysis of recursive batched interpolation search, New trie data structures which support very fast search operations, Interpolation-binary search, Jump interpolation search trees and symmetric binary numbers, Controlled density sorting, 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, Understanding the complexity of interpolation search, An algorithmic and complexity analysis of interpolation search, Simulating interpolation search, Operations research applications of dichotomous 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), Improved bounds for finger search on a RAM, Dynamic interpolation search revisited, Unnamed Item