Inspired by 163B - Lemmings.

Let us have an unknown rational number presented as an irreducible fraction 0 ≤ p / q ≤ 1, where denominator does not exceed Q (in this task — 10⁹). We have a function which determines whether given rational number is less than, greater than or equal to that unknown number (intf (p, q) → {1, 0,  - 1}). The problem is to quess an unknown number using only f(). It is impossible to call f(x, y) where either x or y exceeds Q. Floating point arithmetic is also prohibited. How fast can this problem be solved? Usual binary search is impossible, because it uses rational number's value but not it's numeric representation.

First idea: iterate through a denominator's value and find a numerator using binary search. Asymptothics is O(Q·logQ), which is too slow.

Second solution uses Farey series idea and binary search idea too. Assume we have an interval which contains an unknown number bounded by p_l / q_l и p_r / q_r, initially equal to 0 и 1 respectively. On each step find p_m / q_m, where p_m = p_r + p_l, q_m = q_r + q_l, calculate f(p_m, q_m) and continue doing this with left or right part of an interval respectively. In at most q steps we should get a required fraction (it's easily prooved using Farey series). Asymptothics is O(Q). I want to have O(logQ) or at least something sublinear (o(Q)).

I think, that this problem is rather old and stupid and I reinvent the wheel solving it. How can it be solved?