# Bayesian Binary Search
## 2 Methodology
### Probabilistic Bisection Step  
BBS leverages a probabilistic bisection step. Instead of dividing the search space at the midpoint, BBS divides it at the median of the current PDF. Formally, at each step, we find \(x^{*}\), such that  
\[\int_{low}^{x^{*}}p(x)dx=\int_{x^{*}}^{high}p(x)dx=0.5 \tag{1}\]  
After each comparison, we update the PDF based on the result. If the target is found to be in the lower half, we set \(p(x)=0\) for \(x>x^{*}\) and renormalize the PDF. Similarly, if the target is in the upper half, we set \(p(x)=0\) for \(x<x^{*}\) and renormalize. As proven above, this step is mathematically equivalent to the posterior update step when viewing the algorithm from the lens of Bayesian inference. We evaluate BBS against a basic binary search on both simulated data across several distributions and a real-world example of binary search/bisection of probing channels in the Bitcoin Lightning Network, for which accessing the search space is an expensive operation (time and liquidity) [20]. We further perform a thorough theoretical analysis located in Appendix A. ```
Input:low \(\in\mathbb{Z}\), high \(\in\mathbb{Z}\), \(\epsilon>0\) Output:Target bound with \(\epsilon\) tolerance, or \(-1\) if not found
1\(p(x)\leftarrow\)EstimatePDF(low, high) whilelow \(\leq\)highdo
2\(x^{*}\leftarrow\)FindMedian(\(p(x)\), low, high)
3\(s\leftarrow\)Sign(\(x^{*}\)) ifhigh \(-\)low \(\leq\)\(\epsilon\)then
4 returnlow,high
5 elseif\(s>0\)then
6 high \(\gets\)\(x^{*}\)
7 else
8 low \(\gets\)\(x^{*}\)
9
10 end if
11\(p(x)\leftarrow\)UpdatePDF(\(p(x)\), low, high)
12
13 end if
14 return\(-1\);
```  
**Algorithm 1**Bayesian Binary Search  
```
1 FunctionEstimatePDF(low, high)://Estimate the initial PDF based on the search space // This implementation can vary depending on the available data but can include supervised probabilistic machine learning algorithms or unsupervised statistical methods for distribution estimation return\(p(x)\)
```  
**Algorithm 2**Estimate Search Space Probability Density Function (PDF)  
```
1 FunctionFindMedian(\(p(x)\), low, high):return\(\arg\min_{x\in[\text{low,high}]}|\int_{\text{low}}^{x}p(t)dt-0.5|\)
```  
**Algorithm 3**FindMedian Function  
```
1 FunctionUpdatePDF(\(p(x)\), low, high):if\(x\in[\text{low,high}]\)then
2\(p_{\text{new


```
1 FunctionSign(\(x\)):// This function should be implemented based on the specific problem // It should return -1 if x is less than or equal to the target, 1 if x is greater than the target if\(x>\)targetthen
2 return1 else
3 return\(-1\)
4 end if
```
**Algorithm 5**Sign Function

## 3 Experiments

### Experiments on Simulated Data

We evaluated the performance of BBS against binary search on simulated data from several distributions: normal, bimodal, and exponential. The results of the normal distribution experiments are shown below, while the results of the bimodal and exponential distributions can be found in Appendix A. We additionally show experiments for which the estimated search space density function does not match the target search space as measured by Kullback-Leibler (KL) divergence. We demonstrate how BBS performance degrades as the estimated search space density drifts further from the target distribution, and eventually can cause the BBS to perform worse than basic binary search. #### 3.1.1 Experimental Setup

To evaluate the performance of BBS compared to the standard binary search in the context of normal distributions, we conducted a series of experiments with the following setup. #### 3.1.2 Distribution Parameters

For the normal distribution experiments, we used the following parameters:

* **Mean (\(\mu\))**: 0;
* **Standard Deviation (\(\sigma\))**: 10,000. #### 3.1.3 Target Value Generation

We generated 1000 target values by sampling from the specified normal distribution. Each target value was obtained by drawing a random sample \(x\) from the distribution and applying the floor function to ensure integer targets: \(target=\text{floor}(x)\).