Databases
StackOverflow2013
Postsdbo
POThe "guess the number" game for arbitrary rational numbers?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POThe "guess the number" game for arbitrary rational numbers?
    text
    copied!<p>I once got the following as an interview question:</p> <blockquote> <p>I'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 "lower," "higher," or "correct."</p> </blockquote> <p>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.</p> <p>The question I have, though, is a slight modification of this problem. Instead of picking a positive integer, suppose that I pick an <strong>arbitrary rational number</strong> between zero and one. My question is: what algorithm can you use to most efficiently determine which rational number I've picked?</p> <p>Right now, the best solution I have can find p/q in at most O(q) time by implicitly walking the <a href="http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree" rel="noreferrer">Stern-Brocot tree</a>, 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?</p> <p>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't seem to find a way to search this space given just greater/equal/less comparisons.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload