  We find a searching method on ordered lists that surprisingly outperforms
binary searching with respect to average query complexity while retaining
minmax optimality. The method is shown to require $O(\log_2\log_2 n)$ queries
on average while never exceeding $\lceil \log_2 n \rceil$ queries in the worst
case, i.e. the minmax bound of binary searching. Our average results assume a
uniform distribution hypothesis similar to those of prevous authors under which
the expected query complexity of interpolation search of $O(\log_2\log_2 n)$ is
known to be optimal. Hence our method turns out to be optimal with respect to
both minmax and average performance. We further provide robustness guarantees
and perform several numerical experiments with both artificial and real data.
Our results suggest that time savings range roughly from a constant factor of
10\% to 50\% to a logarithmic factor spanning orders of magnitude when
different metrics are considered.
