I'm trying to design an algorithm that finds a number in a given range. The only signal we get for a given guess is: "Is our guess less than the magic number?" I'm trying to:

  1. Optimize the number of steps it takes to reach the magic number
  2. Minimize how much we overshoot the magic number by

Example: Our range is [1, 1000], and the magic number is 538. We don't want to guess randomly, because that could risk overshooting the magic number by a lot if we guess 100, so it makes sense to start high (1000) and work our way down by some delta, but we don't want to take too many steps, so the delta should probably be some number that's not too big and not too small.

Not sure if this is a coherent problem. I'm wondering if there's an existing algorithm that can solve a problem like this.

My first attempt at doing this involves several rounds of decrementing until we get our signal that we overshot the magic number and then incrementing until we're higher again. Each round we make the increments and decrements more granular so we'll know we've found the magic number if we increment by 1 and our guess is no longer smaller than the magic number.

  • 1
    $\begingroup$ If you want the answer spoiled, Google "binary search". $\endgroup$ – orlp Mar 3 at 22:28
  • $\begingroup$ That would work if I didn't want to minimize how much we miss the magic number by. E.g., if the magic number was 900, the first step of binary search would lead us to guess 500, which is pretty far from 900. $\endgroup$ – Kaiser Octavius Mar 3 at 22:30
  • 1
    $\begingroup$ And what if the magic number was 100? Always guessing the middle minimizes, on average, the error, unless you have prior knowledge about how the magic number is distributed. $\endgroup$ – orlp Mar 3 at 22:39
  • 1
    $\begingroup$ I find it unclear what you mean about the overshoot. Are you trying to minimize that for the final guess, or for the guess used at each step? If so, how do you want to combine all the overshoots at each step into a single number to minimize? The obvious way to minimize the overshoot for the final answer is to do enough steps that you get the final answer exactly correct. $\endgroup$ – D.W. Mar 3 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.