# Robust and adaptive search

arXiv: https://arxiv.org/abs/1702.05932 · HTML: https://mlsanity.com/paper/1702.05932/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2017.

## Built on by (most cited first, 1 of 1)

- [Online Search With Best-Price and Query-Based Predictions](https://mlsanity.com/paper/2112.01592/) (2021)

## Abstract (arXiv)

Binary search finds a given element in a sorted array with an optimal number of log n 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 log n + ck, (1+varepsilon)log n + ck, and √cnk+o(nk) are best-possible for parameter value k, any varepsilon>0, and constant c.