Biased binary search?
Change the binary search procedure to pick a weighted midpoint at each time step:

1.  Input: Search key K, sorted array A, probability distribution P.
2.  Initialize m=0, M=n=len(A)=len(P).
3.  Repeat:
4.     Pick i with m &lt;= i &lt; M such that
5.       sum(P[j] for m&lt;=j&lt;i) &lt;= sum(P[j] for m&lt;=j&lt;M)/2
6.     and
7.       sum(P[j] for i&lt;j&lt;M) &lt;= sum(P[j] for m&lt;=j&lt;M)/2.
8.     Compare K with A[i].
9.     If K==A[i], return i.
10.    If K&lt;A[i], set M=i.
11.    If K&gt;A[i], set m=i+1.
12.    If m==M, return -1. (Fail.)

Suppose the search key is in the array - i.e., K==A[i] for some i. The algorithm halves the value sum(P[j] for m&lt;=j&lt;M) after each iteration. Moreover, this sum starts at 1 and must always be at least P[i]. Thus the number of comparisons is at most 1+log_2(1/P[i]).

If you want to retain the $O(\log n)$ worst case performance, you can mix a bit of the uniform distribution into your distribution. That is, run the algorithm with P'=(P+U)/2, where U is the uniform distribution. Then the number of iterations is at most 1 + log_2(1/P'[i]) &lt;= 2 + min{ log_2(1/P[i]), log_2(n) }.