I once got the following as an interview question:

&gt; I&#39;m thinking of a positive integer n.  Come up with an algorithm that can guess it in O(lg n) queries.  Each query is a number of your choosing, and I will answer either &quot;lower,&quot; &quot;higher,&quot; or &quot;correct.&quot;

This problem can be solved by a modified binary search, in which you listing powers of two until you find one that exceeds n, then run a standard binary search over that range.  What I think is so cool about this is that you can search an infinite space for a particular number faster than just brute-force.

The question I have, though, is a slight modification of this problem.  Instead of picking a positive integer, suppose that I pick an **arbitrary rational number** between zero and one.  My question is: what algorithm can you use to most efficiently determine which rational number I&#39;ve picked?

Right now, the best solution I have can find p/q in at most O(q) time by implicitly walking the [Stern-Brocot tree][1], a binary search tree over all the rationals.  However, I was hoping to get a runtime closer to the runtime that we got for the integer case, maybe something like O(lg (p + q)) or O(lg pq).  Does anyone know of a way to get this sort of runtime?

I initially considered using a standard binary search of the interval [0, 1], but this will only find rational numbers with a non-repeating binary representation, which misses almost all of the rationals.  I also thought about using some other way of enumerating the rationals, but I can&#39;t seem to find a way to search this space given just greater/equal/less comparisons.

  [1]: http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree

All Rational Numbers Solutions on Gang of Coders

Total of 1 Rational Numbers Solutions

The "guess the number" game for arbitrary rational numbers?