The distribution search: An O (n) expected time search
Xusong Xu, Liu Dachang, Zhou Jianqin, Zheng Songyong · Wuhan University Journal of Natural Sciences · 1996
Provided an algorithm for the distribution search and proves the time complexity of the algorithm. This algorithm uses a mathematical formula to search n elements in the sequence of n elements in O ( n ) expected time, and experimental reesult proves that distribution search is superior to binary search.