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

Answer 2

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 }
  }
  return -1; // not found
}

function compare(item, needle) {
  return item - needle;
}

search_state = { last: 0 };
binarySearchBiased(haystack, needle, compare, search_state);

this is (obviously) optimized for 'sequential search' where last_needle and current_needle are very similar, aka 'neighbor search'