  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
$\sqrt{cnk}+o(nk)$ are best-possible for parameter value $k$, any
$\varepsilon>0$, and constant $c$.
