Most efficient way to determine lowest valid number within a big range by only knowing whether your guess is too low

Let’s assume you want to guess a certain number(x) within a big range in Python.

A simple external validation function, which you can call as many times as needed, will give you hints:

• If the number being tested is equal to or higher than the lowest valid number, it will, in both cases, return True (you may not know explicitly if the number being tested is too high).
• Else (if the number is too low) it will return False.

What would be the most efficient way to determine the smallest possible valid number? Is there a non-linear approach?

Answer

I don’t know about most efficient, but here is a quite efficient algorithm. It first searches the order of magnitude by taking successive powers of 2. Then it uses dichotomy to narrow down the actual number:

num = 123

lowest = 0
guess  = 1

check = lambda : guess >= num

i=0
# find order of magnitude
while not check():
    i+=1
    #print(guess)
    lowest = guess
    guess = guess*2

# find number
highest = guess
while lowest != highest-1:
    i+=1
    guess = (highest+lowest)//2
    #print(lowest, guess, highest)
    if check():
        highest = guess
    else:
        lowest = guess
        
guess = highest

print(f'found {guess} in {i} steps')

Example with 123: found 123 in 13 steps

Example with 123456789: found 123456789 in 53 steps

NB. You can uncomment the print to see the intermediate steps