DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.35

Fast Rational Search via Stern-Brocot Tree

Authors: Connor Weyers and N. V. Vinodchandran

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

We revisit the problem of rational search: given an unknown rational number α = a/b ∈ (0,∞) with a,b ≤ n, the goal is to identify α using comparison queries of the form "β ≤ α?". The problem has been studied several decades ago and optimal query algorithms are known. We present an algorithm for rational search based on a compressed traversal of the Stern-Brocot tree, which appeared to have been overlooked in the literature. This approach also naturally extends to two related problems that, to the best of our knowledge, have not been previously addressed: (i) unbounded rational search, where the bound n is unknown, and (ii) computing the best (in a precise sense) rational approximation of an unknown real number using only comparison queries. While the algorithm is simple and natural, one of our main contributions is its analysis: we give an upper and lower bound on its worst-case query complexity.

Cite as

Connor Weyers and N. V. Vinodchandran. Fast Rational Search via Stern-Brocot Tree. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{weyers_et_al:LIPIcs.MFCS.2026.35,
  author =	{Weyers, Connor and Vinodchandran, N. V.},
  title =	{{Fast Rational Search via Stern-Brocot Tree}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.35},
  URN =		{urn:nbn:de:0030-drops-274169},
  doi =		{10.4230/LIPIcs.MFCS.2026.35},
  annote =	{Keywords: Rational number search, Continued fractions, Stern-Brocot tree, Rational approximation}
}

Search Results

Documents authored by Weyers, Connor

Fast Rational Search via Stern-Brocot Tree

Abstract

Cite as

Thanks for your feedback!

Could not send message