Robust and adaptive search

DOI10.4230/LIPICS.STACS.2017.26MaRDI QIDQ4636624zbMATH OpenOpenAlexFDO

Authors Y. Disser, Stefan Kratsch

Publication date 19 April 2018

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

zbMATH Keywords

robustnessadaptive algorithmssearchingmemory faultsarray disorder

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Abstract: Binary search finds a given element in a sorted array with an optimal number of $logn$ queries. However, binary search fails even when the array is only slightly disordered or access to its elements is subject to errors. We study the worst-case query complexity of search algorithms that are robust to imprecise queries and that adapt to perturbations of the order of the elements. We give (almost) tight results for various parameters that quantify query errors and that measure array disorder. In particular, we exhibit settings where query complexities of $logn+ck$, $(1+varepsilon)logn+ck$, and $sqrtcnk+o(nk)$ are best-possible for parameter value $k$, any $varepsilon>0$, and constant $c$.

Recommendations

• Coping with errors in binary search procedures (Preliminary Report)
• Searching with known error probability
• Weakly adaptive comparison searching
• scientific article; zbMATH DE number 1444319
• Adaptive search over sorted sets

Cited in

(4)

• Reactive search and intelligent optimization
• On adaptive algorithms for maximum matching
• No sorting? Better searching!
• Noisy binary search and its applications

This page was built for publication: Robust and adaptive search

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