Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?

Question

I thought of some mixed algorithm: binary + interpolation search. While first has $O(\log n)$ runtime in both worst and average cases, second has $O(n)$ worst case runtime and $O(\log \log n)$ average case.

However, I think, if such algorithms can exist, there are more than one of them.

Anyway, what I want to know if there is any known algorithm with restrictions given in title.

Note. It must be appliable to simple arrays without repeatitions (no precomputing/hashing).

Answer 1

Yup. Do interpolation search, but after $\log n$ iterations, if you haven't found the answer yet, switch to binary search. This ensures a $O(\log n)$ worst-case running time, while retaining the $O(\log \log n)$ average-case running time. Note that the average case only applies if you make a particular assumption about the distribution of values in the array.