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:
- Optimize the number of steps it takes to reach the magic number
- 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.