Interpolation search [1], which allows you to search a sorted array in O(log(log(n))) time, assuming its elements are uniformly distributed (for instance, you are searching a sorted array of hashes.)

[1] https://en.wikipedia.org/wiki/Interpolation_search