title: Guessing an unbounded integer
body: <p>If I say to you:</p>
  
  <p>"I am thinking of a number between 0 and n, and I will tell you if your guess is high or low", then you will immediately reach for binary search.</p>
  
  <p>What if I remove the upper bound? i.e. I am thinking of a positive integer, and you need to guess it.</p>
  
  <p>One possible method would be for you to guess 2, 4, 8, ..., until you guess 2**k for some k and I say "lower".  Then you can apply binary search.</p>
  
  <p>Is there a quicker method?</p>
  
  <p>EDIT:</p>
  
  <p>Clearly, any solution is going to take time proportional to the size of the target number.  If I chuck Graham's number through the Ackermann function, we'll be waiting a while whatever strategy you pursue.</p>
  
  <p>I could offer this algorithm too: Guess each integer in turn, starting from 1.</p>
  
  <p>It's guaranteed to finish in a finite amount of time, but yet it's clearly much worse than my "powers of 2" strategy.  If I can find a worse algorithm (and know that it is worse), then maybe I could find a better one?</p>
  
  <p>For example, instead of powers of 2, maybe I can use powers of 10.  Then I find the upper bound in <code>log_10(n)</code> steps, instead of <code>log_2(n)</code> steps.  But I have to then search a bigger space.  Say <code>k = ceil(log_10(n))</code>.  Then I need <code>log_2(10**k - 10**(k-1))</code> steps for my binary search, which I guess is about <code>10+log_2(k)</code>.  For powers of 2, I have roughly <code>log_2(log_2(n))</code> steps for my search phase.  Which wins?</p>
  
  <p>What if I search upwards using <code>n**n</code>?  Or some other sequence?  Does the prize go to whoever can find the sequence that grows the fastest?  Is this a problem with an answer?</p>
  
  <p>Thank you for your thoughts.  And my apologies to those of you suggesting I start at MAX_INT or 2**32-1, since I'm clearly drifting away from the bounds of practicality here.</p>
  
  <p>FINAL EDIT:</p>
  
  <p>Hi all,</p>
  
  <p>Thank you for your responses.  I accepted the answer by Norman Ramsey (and commenter onebyone) for what I understood to be the following argument: for a target number n, any strategy must be capable of distinguishing between (at least) the numbers from 0..n, which means you need (at least) O(log(n)) comparisons.</p>
  
  <p>However seveal of you also pointed out that the problem is not well-defined in the first place, because it's not possible to pick a "random positive integer" under the uniform probability distribution (or, rather, a uniform probability distribution cannot exist over an infinite set).  And once I give you a nonuniform distribution, you can split it in half and apply binary search as normal.</p>
  
  <p>This is a problem that I've often pondered as I walk around, so I'm pleased to have two conclusive answers for it.</p>