# Biased binary search?

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?

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

• An alternative (and probably simpler to implement) method of retaining $O(\log n)$ performance is to choose some constant $0 < c \leq \frac{1}{2}$ and letting your chosen index $i' = \text{clamp}(i, cn, (1-c)n)$. – orlp Oct 10 '20 at 12:57

expand and reduce search:

start with the bias value (guess, last), expand the search range step-by-step to find the nearest low and high values (low < actual < high), then reduce the search range to find the actual value

here an implementation in javascript (sorry for not being theoretical) (even less theoretical: a benchmark)

function binarySearchBiased(haystack, needle, comparator, state) {
// find nearest low and high values = expand search range
let cmp = comparator(haystack[state.last], needle);
if (cmp == 0) return state.last;
function found(val) { state.last = val; return val }
let low, high;
const max_high = haystack.length - 1;
if (cmp > 0) { // item > needle
high = state.last;
// find nearest low value
for (let diff = 1; ; diff *= 2) {
low = high - diff;
if (low < 0) { low = 0; break }
let cmp = comparator(haystack[low], needle);
if (cmp == 0) return found(low);
if (cmp < 0) break; // item < needle
high = low - 1; // exclude low from range
}
}
else { // item < needle
low = state.last;
// find nearest high value
for (let diff = 1; ; diff *= 2) {
high = low + diff;
if (high > max_high) { high = max_high; break }
let cmp = comparator(haystack[high], needle);
if (cmp == 0) return found(high);
if (cmp > 0) break; // item > needle
low = high + 1; // exclude high from range
}
}

// binary search = reduce search range
while (low <= high) {
const mid = low + ((high - low) >> 1);
const cmp = comparator(haystack[mid], needle);
if (cmp == 0) return found(mid);
if (cmp < 0) { low = mid + 1 }
else { high = mid - 1 }
}