<p>In a standard binary search on a sorted array, when you compare the item being searched (<span class="math-container">$x$</span>) with the pivot (<span class="math-container">$m$</span>), if <span class="math-container">$x &lt; m$</span>, then you recurse in the first half of the array; if <span class="math-container">$x &gt; m$</span>, then you recurse in the second half of the array;</p>
<p>I'm looking for literature on binary search where the comparison function isn't always accurate, i.e., doesn't give you perfect information on which side to recurse.</p>
<p>Specifically, I'm looking for the following: let's say we have a comparator <span class="math-container">$C(\cdot, \cdot)$</span>.</p>
<p>If <span class="math-container">$C(x,m) = -1$</span>, then <span class="math-container">$x$</span> will be in the first part of the array with 100% probability</p>
<p>If <span class="math-container">$C(x,m) = 0$</span>, then we've found <span class="math-container">$x = m$</span></p>
<p>If <span class="math-container">$C(x,m) = 1$</span>, then <span class="math-container">$x$</span> will be in the first part of the array with probability <span class="math-container">$p$</span> and in the second part with probability <span class="math-container">$1-p$</span></p>

CC BY-SA 4.0
2024-10-12T06:21:56.293Z
https://en.wikipedia.org/wiki/Binary_search#Noisy_binary_search
D.W.
CC BY-SA 4.0
2024-10-12T06:37:09.673Z
What is the algorithm used to implement $C$?  In particular, if $x<m$, what is the probability that $C(x,m)=-1$ and the probability that $C(x,m)=1$?  (What if $m<pn$ where $n$ is the length of the array?  Then your specification does not seem achievable?)
D.W.
CC BY-SA 4.0
2024-10-13T11:27:12.270Z
Thanks. Is there a version with only one-sided errors? So if the comparison says x<m or x=m, then it is always correct but if it says x>m, the truth is that it is actually x<m with probability p and x>m with probability 1-p
John White
CC BY-SA 4.0
2024-10-13T11:35:58.820Z
The comparator is a black box. I'm using C(x,m) =-1 (resp 1) as the comparator claiming that x<m (resp x>m). When the comparator claims x>m, it is incorrect with probability p
John White
CC BY-SA 4.0
2024-10-13T23:14:05.950Z
Thank you for your response.  I think I understand the intent, but I don't think you've fully appreciated some of my comments yet.  If $m<pn$, where $n$ is the length of the array, then I believe it is not possible to build a comparator with the properties you want it to have.  So please specify how $C$ operators -- not just what we can infer from its output, but what randomized algorithm $C$ uses to produce an output, given the inputs.
D.W.
<ds.algorithms>
Binary Search with Probabilistic Comparison Errors
John White
# Binary Search with Probabilistic Comparison Errors

(Asked by: username_0 on 2024-10-12)

In a standard binary search on a sorted array, when you compare the item being searched ($x$) with the pivot ($m$), if $x < m$, then you recurse in the first half of the array; if $x > m$, then you recurse in the second half of the array;

I'm looking for literature on binary search where the comparison function isn't always accurate, i.e., doesn't give you perfect information on which side to recurse.

Specifically, I'm looking for the following: let's say we have a comparator $C(\cdot, \cdot)$.

If $C(x,m) = -1$, then $x$ will be in the first part of the array with 100% probability

If $C(x,m) = 0$, then we've found $x = m$

If $C(x,m) = 1$, then $x$ will be in the first part of the array with probability $p$ and in the second part with probability $1-p$

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: https://en.wikipedia.org/wiki/Binary_search#Noisy_binary_search  
> **username_1**: What is the algorithm used to implement $C$?  In particular, if $x<m$, what is the probability that $C(x,m)=-1$ and the probability that $C(x,m)=1$?  (What if $m<pn$ where $n$ is the length of the array?  Then your specification does not seem achievable?)  
> **username_0**: Thanks. Is there a version with only one-sided errors? So if the comparison says x<m or x=m, then it is always correct but if it says x>m, the truth is that it is actually x<m with probability p and x>m with probability 1-p  
> **username_0**: The comparator is a black box. I'm using C(x,m) =-1 (resp 1) as the comparator claiming that x<m (resp x>m). When the comparator claims x>m, it is incorrect with probability p  
> **username_1**: Thank you for your response.  I think I understand the intent, but I don't think you've fully appreciated some of my comments yet.  If $m<pn$, where $n$ is the length of the array, then I believe it is not possible to build a comparator with the properties you want it to have.  So please specify how $C$ operators -- not just what we can infer from its output, but what randomized algorithm $C$ uses to produce an output, given the inputs.  

---

## 0 answers

