<p>Change the binary search procedure to pick a weighted midpoint at each time step:</p>

<p><code>1.  Input: Search key K, sorted array A, probability distribution P.</code><br>
<code>2.  Initialize m=0, M=n=len(A)=len(P).</code><br>
<code>3.  Repeat:</code><br>
<code>4.     Pick i with m &lt;= i &lt; M such that</code><br>
<code>5.       sum(P[j] for m&lt;=j&lt;i) &lt;= sum(P[j] for m&lt;=j&lt;M)/2</code><br>
<code>6.     and</code><br>
<code>7.       sum(P[j] for i&lt;j&lt;M) &lt;= sum(P[j] for m&lt;=j&lt;M)/2.</code><br>
<code>8.     Compare K with A[i].</code><br>
<code>9.     If K==A[i], return i.</code><br>
<code>10.    If K&lt;A[i], set M=i.</code><br>
<code>11.    If K&gt;A[i], set m=i+1.</code><br>
<code>12.    If m==M, return -1. (Fail.)</code></p>

<p>Suppose the search key is in the array - i.e., <code>K==A[i]</code> for some <code>i</code>. The algorithm halves the value <code>sum(P[j] for m&lt;=j&lt;M)</code> after each iteration. Moreover, this sum starts at 1 and must always be at least <code>P[i]</code>. Thus the number of comparisons is at most <code>1+log_2(1/P[i])</code>.</p>

<p>If you want to retain the <span class="math-container">$O(\log n)$</span> worst case performance, you can mix a bit of the uniform distribution into your distribution. That is, run the algorithm with <code>P'=(P+U)/2</code>, where <code>U</code> is the uniform distribution. Then the number of iterations is at most <code>1 + log_2(1/P'[i]) &lt;= 2 + min{ log_2(1/P[i]), log_2(n) }</code>.</p>

CC BY-SA 4.0
2020-10-10T12:57:13.180Z
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
CC BY-SA 4.0
2019-05-06T23:37:58.313Z
2019-05-06T23:37:58.313Z
Thomas Steinke
<p>expand and reduce search:</p>
<p>start with the <code>bias</code> value (<code>guess</code>, <code>last</code>), expand the search range step-by-step to find the nearest <code>low</code> and <code>high</code> values (<code>low &lt; actual &lt; high</code>), then reduce the search range to find the <code>actual</code> value</p>
<p>here an implementation in javascript (sorry for not being theoretical) (even less theoretical: <a href="http://jsbench.github.io/#24ecbbbc5d760eb771f776b227d8c36b" rel="nofollow noreferrer">a benchmark</a>)</p>
<pre><code>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 &gt; 0) { // item &gt; needle
    high = state.last;
    // find nearest low value
    for (let diff = 1; ; diff *= 2) {
      low = high - diff;
      if (low &lt; 0) { low = 0; break }
      let cmp = comparator(haystack[low], needle);
      if (cmp == 0) return found(low);
      if (cmp &lt; 0) break; // item &lt; needle
      high = low - 1; // exclude low from range
    }
  }
  else { // item &lt; needle
    low = state.last;
    // find nearest high value
    for (let diff = 1; ; diff *= 2) {
      high = low + diff;
      if (high &gt; max_high) { high = max_high; break }
      let cmp = comparator(haystack[high], needle);
      if (cmp == 0) return found(high);
      if (cmp &gt; 0) break; // item &gt; needle
      low = high + 1; // exclude high from range
    }
  }

  // binary search = reduce search range
  while (low &lt;= high) {
    const mid = low + ((high - low) &gt;&gt; 1);
    const cmp = comparator(haystack[mid], needle);
    if (cmp == 0) return found(mid);
    if (cmp &lt; 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);
</code></pre>
<p>this is (obviously) optimized for 'sequential search' where last_needle and current_needle are very similar, aka 'neighbor search'</p>

CC BY-SA 4.0
2020-10-09T08:41:55.367Z
2020-10-10T08:19:09.403Z
2020-10-10T08:19:09.403Z
milahu
<p>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 <span class="math-container">$P(i)$</span> that tells me the probability of the goal element being found at position <span class="math-container">$i$</span>.</p>

<p>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 <span class="math-container">$\Theta(\log N)$</span> asymptotic performance of binary search by using <span class="math-container">$P(i)$</span> to inform my choice of pivot at each step. If this is indeed a good idea, how should it be done?</p>

<search-problem>
Biased binary search?
Display Name
# Biased binary search?

(Asked by: username_0 on 2019-05-06)

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?

**Tags:** search-problem


---

## 2 answers

### Answer by username_1 on 2019-05-06. Score: 2 | Accepted answer

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  
6. and  
7. sum(P[j] for i  
8. Compare K with A[i].  
9. If K==A[i], return i.  
10. If K  
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 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) }`.

> **Comments:**
> **username_2**: 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)$.  

---

### Answer by username_3 on 2020-10-09. Score: 0

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'


---

