Interpolation search—a log log N search

DOI10.1145/359545.359557MaRDI QIDQ4157947zbMATH OpenOpenAlexWikidataFDO

Authors 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

General topics in the theory of software (68N01) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99)

Cited in

(20)

• Expected complexity of fast search with uniformly distributed data
• Analysis of recursive batched interpolation search
• scientific article; zbMATH DE number 3829247 (Why is no real title available?)
• Simulating interpolation search
• Interpolation-binary search
• A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
• Parallel processing can be harmful: The unusual behavior of interpolation search
• Operations research applications of dichotomous search
• Log-logarithmic worst-case range queries are possible in space theta(N)
• 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
• Jump interpolation search trees and symmetric binary numbers
• Controlled density sorting
• Improved bounds for finger search on a RAM
• Data Structures for Data-Intensive Applications: Tradeoffs and Design Guidelines
• New trie data structures which support very fast search operations
• Understanding the complexity of interpolation search
• An algorithmic and complexity analysis of interpolation search
• Dynamic interpolation search revisited

This page was built for publication: Interpolation search—a log log N search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4157947)