{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T15:37:18Z","timestamp":1769096238053,"version":"3.49.0"},"reference-count":25,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T00:00:00Z","timestamp":1753142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Stillmark and Amboss Technologies"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We present Bayesian Binary Search (BBS), a novel framework that bridges statistical learning theory\/probabilistic machine learning and binary search. BBS utilizes probabilistic methods to learn the underlying probability density of the search space. This learned distribution then informs a modified bisection strategy, where the split point is determined by probability density rather than the conventional midpoint. This learning process for search space density estimation can be achieved through various supervised probabilistic machine learning techniques (e.g., Gaussian Process Regression, Bayesian Neural Networks, and Quantile Regression) or unsupervised statistical learning algorithms (e.g., Gaussian Mixture Models, Kernel Density Estimation (KDE), and Maximum Likelihood Estimation (MLE)). Our results demonstrate substantial efficiency improvements using BBS on both synthetic data with diverse distributions and in a real-world scenario involving Bitcoin Lightning Network channel balance probing (3\u20136% efficiency gain), where BBS is currently in production.<\/jats:p>","DOI":"10.3390\/a18080452","type":"journal-article","created":{"date-parts":[[2025,7,22]],"date-time":"2025-07-22T08:45:18Z","timestamp":1753173918000},"page":"452","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Bayesian Binary Search"],"prefix":"10.3390","volume":"18","author":[{"given":"Vikash","family":"Singh","sequence":"first","affiliation":[{"name":"Stillmark, Los Angeles, CA 90293, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Khanzadeh","sequence":"additional","affiliation":[{"name":"Independent Researcher, Los Angeles, CA 90293, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Davis","sequence":"additional","affiliation":[{"name":"Amboss Technologies, Nashville, TN 37212, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harrison","family":"Rush","sequence":"additional","affiliation":[{"name":"Amboss Technologies, Nashville, TN 37212, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Emanuele","family":"Rossi","sequence":"additional","affiliation":[{"name":"Amboss Technologies, Nashville, TN 37212, USA"},{"name":"VantAI, New York, NY 10003, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesse","family":"Shrader","sequence":"additional","affiliation":[{"name":"Amboss Technologies, Nashville, TN 37212, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pietro","family":"Lio\u2019","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Technology, University of Cambridge, Cambridge CB3 0FD, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,7,22]]},"reference":[{"key":"ref_1","unstructured":"Knuth, D.E. (1998). The Art of Computer Programming: Volume 3: Sorting and Searching, Addison-Wesley Professional."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1147\/rd.12.0130","article-title":"Addressing for random-access storage","volume":"1","author":"Peterson","year":"1957","journal-title":"IBM J. Res. Dev."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1090\/psapm\/010\/0113289","article-title":"Teaching combinatorial tricks to a computer","volume":"10","author":"Lehmer","year":"1960","journal-title":"Proc. Sympos. Appl. Math."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Bottenbruch, H. (1962). Structure and use of algol 60. Symbolic Languages in Data Processing, Gordon and Breach.","DOI":"10.2172\/4020495"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Chazelle, B., and Guibas, L.J. (1986). Fractional cascading: I. A data structuring technique. Algorithmica, Springer.","DOI":"10.1007\/BF01840440"},{"key":"ref_6","first-page":"1072","article-title":"Interpolated binary search: An efficient hybrid search algorithm on ordered datasets","volume":"24","author":"Mohammed","year":"2021","journal-title":"Eng. Sci. Technol. Int. J."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Lin, J.-L. (2024). Interpolation Once Binary Search over a Sorted List. Mathematics, 12.","DOI":"10.20944\/preprints202404.0896.v1"},{"key":"ref_8","unstructured":"Lin, H., Luo, T., and Woodruff, D. (2022). Learning augmented binary search trees. International Conference on Machine Learning, PMLR."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Russ, S. (2004). The Mathematical Works of Bernard Bolzano, Oxford University Press.","DOI":"10.1093\/oso\/9780198539308.001.0001"},{"key":"ref_10","unstructured":"Burden, R.L., and Faires, J.D. (2015). Numerical Analysis, Cengage Learning."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1109\/TIT.1963.1057832","article-title":"Sequential transmission using noiseless feedback","volume":"9","author":"Horstein","year":"1963","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_12","first-page":"173","article-title":"Global optimization using interval analysis: The multi-dimensional case","volume":"21","author":"Hansen","year":"1991","journal-title":"Comput. Math. Appl."},{"key":"ref_13","unstructured":"Waeber, R., Frazier, P.I., and Henderson, S.G. (2011, January 11\u201314). A bayesian approach to stochastic root finding. Proceedings of the 2013 Winter Simulation Conference, Phoenix, AZ, USA."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1239\/jap\/1331216837","article-title":"Twenty questions with noise: Bayes optimal policies for entropy loss","volume":"49","author":"Jedynak","year":"2012","journal-title":"J. Appl. Probab."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"731","DOI":"10.1145\/355588.365137","article-title":"Parallel methods for integrating ordinary differential equations","volume":"7","author":"Nievergelt","year":"1964","journal-title":"Commun. ACM"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1038\/nature14541","article-title":"Probabilistic machine learning and artificial intelligence","volume":"521","author":"Ghahramani","year":"2015","journal-title":"Nature"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Rasmussen, C.E., and Williams, C.K. (2006). Gaussian Processes for Machine Learning, MIT Press.","DOI":"10.7551\/mitpress\/3206.001.0001"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"3395","DOI":"10.1109\/TKDE.2016.2606428","article-title":"Towards bayesian deep learning: A framework and some existing methods","volume":"28","author":"Wang","year":"2016","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1109\/JPROC.2015.2494218","article-title":"Taking the human out of the loop: A review of bayesian optimization","volume":"104","author":"Shahriari","year":"2015","journal-title":"Proc. IEEE"},{"key":"ref_20","unstructured":"Tikhomirov, S., Pickhardt, R., Biryukov, A., and Nowostawski, M. (2020). Probing channel balances in the lightning network. arXiv."},{"key":"ref_21","unstructured":"Rossi, E., and Singh, V. (2024). Channel balance interpolation in the lightning network via Machine learning. arXiv."},{"key":"ref_22","unstructured":"Rosenblatt, F. (1957). The perceptron\u2014A Perceiving and Recognizing Automaton, Cornell Aeronautical Laboratory. Technical Report 85-460-1."},{"key":"ref_23","unstructured":"Dwivedi, V.P., Joshi, C.K., Laurent, T., Bengio, Y., and Bresson, X. (2020). Benchmarking graph neural networks. arXiv."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF00264563","article-title":"Nearly optimal binary search trees","volume":"5","author":"Mehlhorn","year":"1975","journal-title":"Acta Inform."},{"key":"ref_25","unstructured":"Dinitz, M., Im, S., Lavastida, T., Moseley, B., Niaparast, A., and Vassilvitskii, S. (2024). Binary search with distributional predictions. arXiv."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/8\/452\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T18:13:37Z","timestamp":1760033617000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/8\/452"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,22]]},"references-count":25,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2025,8]]}},"alternative-id":["a18080452"],"URL":"https:\/\/doi.org\/10.3390\/a18080452","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,22]]}}}