# Bayesian Binary Search
## 1 Introduction  
The concept of organizing data for efficient searching has ancient roots. One of the earliest known examples is the Inakibit-Anu tablet from Babylon (c. 200 BCE), which contained approximately 500 sorted sexagesimal numbers and their reciprocals, facilitating easier searches [1]. Similar sorting techniques were evident in name lists discovered on the Aegean Islands. The Catholicon, a Latin dictionary completed in 1286 CE, marked a significant advance by introducing rules for complete alphabetical classification [1]. The documented modern era of search algorithms began in 1946 when [PERSON] first mentioned binary search during the seminal Moore School Lectures [1]. This was followed by [PERSON]'s introduction of interpolation search in 1957 [2]. A limitation of early binary search algorithms was their restriction to arrays with lengths one less than a power of two. This constraint was overcome in 1960 by [PERSON], who published a generalized binary search algorithm applicable to arrays of any length [3]. A significant optimization came in 1962 when [PERSON] presented an ALGOL 60 implementation of binary search that moved the equality comparison to the end of the process [4]. While this increased the average number of iterations by one, it reducedthe number of comparisons per iteration to one, potentially improving efficiency. Further refinements to binary search continued, with [PERSON] of Stanford University developing the uniform binary search in 1971 [1]. This variant aimed to provide more consistent performance across different input distributions. In the realm of computational geometry, [PERSON] and [PERSON] introduced fractional cascading in 1986 [5]. This technique provided a method to efficiently solve various search problems in geometric contexts, broadening the application of search algorithms beyond simple sorted lists. More recently, hybrid and learning-based approaches have gained attention. For instance, ref. [6] proposed a hybrid search algorithm combining binary search and interpolated search, a theme also explored by [7] with an algorithm that performs interpolation once over a binary search. A newer related trend involves improving the binary search tree data structure using a frequency estimation oracle [8]. The bisection method, a fundamental technique in numerical analysis, shares conceptual similarities with binary search. This method, also known as the interval halving method, binary chopping, or [PERSON]'s method, has origins of the bisection method that can be traced back to ancient mathematics. However, its formal description is often attributed to [PERSON]'s work in the early 19 th century [9]. [PERSON]'s theorem, which guarantees the existence of a root in a continuous function that changes sign over an interval, provides the theoretical basis for the bisection method. In the context of root-finding algorithms, ref. [10] provides a comprehensive treatment of the bisection method, discussing its convergence properties and error bounds. They highlight the method's robustness and guaranteed convergence, albeit at a relatively slow linear rate. Variants of the bisection method have been developed to improve efficiency and applicability. Ref. [11] first introduced probabilistic bisection. Ref. [12] employed interval analysis and bisection to develop reliable methods for finding global optima. These studies demonstrate how bisection principles can be extended beyond simple root-finding to more complex optimization problems. The connection between bisection and binary search in computer science was explored by [1], who discussed both methods in the context of searching and optimization algorithms. This connection underlies our approach in leveraging probabilistic techniques to enhance binary search. Recent work has focused on adapting bisection methods to handle uncertainty and noise. Ref. [13] introduced a probabilistic bisection algorithm for noisy root-finding problems.