Replying to @vbuterin (0x1db3439a222c519ab44bb1144fc28167b4fa6ee6)

Did you know: interpolation search https://en.wikipedia.org/wiki/Interpolation_search Achieves O(log(log(n)) average case time on uniformly distributed data.