Interpolation search—a log log N search

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

Mathematics Subject Classification ID

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