Minmax-optimal list searching with $O({\log }_2{\log }_{2}n)$ average cost

I. F. D. Oliveira, R. H. C. Takahashi

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…