What is the meaning of uniform distribution of elements in an array? I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can someone please explain me this?
Suppose that the array $A$ is chosen in the following way:


Sample $n$ real numbers uniformly from the interval $[0,1]$.
Sort the $n$ samples.


Suppose that you choose a further uniform random variable $x$ from the interval $[0,1]$. The expected running time of interpolation search on $A$ and $x$ is $O(\log\log n)$, where the expectation is over the choices of both $A$ and $x$.

In fact, if I understand Gonnet's thesis correctly, the expectation is still $O(\log\log n)$ even for any fixed $x$. See also Gonnet et al.