2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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) }.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.