title: Hot and Cold Binary Search Game
body: <p>Hot or cold.</p>
  
  <p>I think you have to do some sort of binary search but I'm not sure how.</p>
  
  <blockquote>
    <p>Your goal is the guess a secret integer between 1 and N. You
    repeatedly guess integers between 1 and N. After each guess you learn
    if it equals the secret integer (and the game stops); otherwise
    (starting with the second guess), you learn if the guess is hotter
    (closer to) or colder (farther from) the secret number than your
    previous guess. Design an algorithm that finds the secret number in lg
    N + O(1) guesses.</p>
    
    <p>Hint: Design an algorithm that solves the problem in lg N + O(1)
    guesses assuming you are permitted to guess integers in the range -N
    to 2N.</p>
  </blockquote>
  
  <p>I've been racking my brain and I can't seem to come up with a a lg N + O(1).</p>
  
  <p>I found this: <a href="http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1316188034" rel="nofollow">http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1316188034</a> but could not understand the diagram and it did not describe other possible cases.</p>