Adaptive search over sorted sets

DOI10.1016/J.JDA.2014.12.007MaRDI QIDQ2253912zbMATH OpenOpenAlexWikidataFDO

Authors Biagio Bonasera, Emilio Ferrara, Giacomo Fiumara, Francesco Pagano, Alessandro Provetti

Publication date 13 February 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.03845

zbMATH Keywords

sortingsearching sorted sets

Mathematics Subject Classification ID

Searching and sorting (68P10)

Abstract: We revisit the classical algorithms for searching over sorted sets to introduce an algorithm refinement, called Adaptive Search, that combines the good features of Interpolation search and those of Binary search. W.r.t. Interpolation search, only a constant number of extra comparisons is introduced. Yet, under diverse input data distributions our algorithm shows costs comparable to that of Interpolation search, i.e., O(log log n) while the worst-case cost is always in O(log n), as with Binary search. On benchmarks drawn from large datasets, both synthetic and real-life, Adaptive search scores better times and lesser memory accesses even than Santoro and Sidney's Interpolation-Binary search.

Recommendations

• A framework for adaptive sorting
• A framework for adaptive sorting
• scientific article; zbMATH DE number 5540281
• scientific article; zbMATH DE number 861625
• Towards pure adaptive search
• Adaptive stochastic search
• scientific article; zbMATH DE number 4112059
• A general method for improving insertion-based adaptive sorting

Cites work

• scientific article; zbMATH DE number 6469186 (Why is no real title available?)
• Dynamic interpolation search
• Dynamic interpolation search in \(o(\log\log n)\) time
• Interpolation-binary search
• Introduction to algorithms.
• Tight bounds for searching a sorted array of strings

Cited in

(6)

• Robust and adaptive search
• scientific article; zbMATH DE number 5540281 (Why is no real title available?)
• Adaptive linear list reorganization under a generalized query system
• Weakly adaptive comparison searching
• scientific article; zbMATH DE number 861625 (Why is no real title available?)
• Operations research applications of dichotomous search

This page was built for publication: Adaptive search over sorted sets

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