Fast Rational Search via Stern-Brocot Tree

Connor Weyers, N. V. Vinodchandran

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