Have a look at interpolation search.

The complexity is O(log log n), under the assumption of a uniform distribution of the data.

https://en.wikipedia.org/wiki/Interpolation_search