Biased binary search?

Question

Suppose I have some pre-existing knowledge of where within a sorted array the element I am looking for lies, in the form of a probability distribution $P(i)$ that tells me the probability of the goal element being found at position $i$.

When executing a binary search, the pivot has to be chosen at each step. I have a vague sense that I could, somehow, exploit my pre-existing knowledge of the element's location while retaining the $\Theta(\log N)$ asymptotic performance of binary search by using $P(i)$ to inform my choice of pivot at each step. If this is indeed a good idea, how should it be done?

Answer 1

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 <= i < M such that
5. sum(P[j] for m<=j<i) <= sum(P[j] for m<=j<M)/2
6. and
7. sum(P[j] for i<j<M) <= sum(P[j] for m<=j<M)/2.
8. Compare K with A[i].
9. If K==A[i], return i.
10. If K<A[i], set M=i.
11. If K>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<=j<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]) <= 2 + min{ log_2(1/P[i]), log_2(n) }.