Interpolation search—a log log N search

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

Mathematics Subject Classification ID

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