3
$\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) }.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – orlp Oct 10 at 12:57
0
$\begingroup$

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'

| cite | improve this answer | |
$\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.