Robust and adaptive search

DOI10.4230/LIPICS.STACS.2017.26zbMATH Open1402.68035arXiv1702.05932OpenAlexW2593124606MaRDI QIDQ4636624FDOQ4636624

Authors: Y. Disser, Stefan Kratsch 

Publication date: 19 April 2018

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$.

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

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

zbMATH Keywords

robustnessadaptive algorithmssearchingmemory faultsarray disorder

Mathematics Subject Classification ID

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

Cited In (3)

• Title not available (Why is that?)
• Reactive search and intelligent optimization
• Approximate sorting and its applications in I/O model

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)