Binary search works whenever possible answers have an ordered boundary: too small on one side and large enough on the other.

Search a space of possibilities

Suppose a machine can make a certain number of parts each hour. We want the fewest hours needed to reach a target. More time never produces fewer parts, so the answers have a useful order.

  • Choose a low and high possible answer.
  • Test the middle answer.
  • Discard the half that cannot contain the boundary.
  • Keep going until low and high meet.

Ask a yes-or-no question

The test should answer something like: is this amount enough? Once the answer changes from no to yes and never changes back, binary search can locate that first yes.

Find the first number large enoughPython
def first_square_at_least(target):
    low = 0
    high = target

    while low < high:
        middle = (low + high) // 2
        if middle * middle >= target:
            high = middle
        else:
            low = middle + 1

    return low

print(first_square_at_least(20))  # 5

The difficult part is proving the boundary exists and deciding which half is safe to remove. Write that reasoning down before coding.

Your tiny challenge

Think of a number from 1 to 100. After each guess, answer too low or high enough. How many guesses does binary search need?