Fast Rational Search via Stern-Brocot Tree

Connor Weyers, N. V. Vinodchandran

We revisit the problem of rational search: given an unknown rational number $\hat{I}\pm =\frac{a}{b}\in (0,1)$ with $b\le n$, the goal is to identify $\hat{I}\pm$ using comparison queries of th…