🎓 A1Learner
🔍
0 of 47 lessons completed

Binary Search on the Answer

Binary search on the answer is a way to search a range of possible results instead of a list. It fits when a guess can be checked as too small or too big.

Spot the signal

A problem asks for the smallest working value, and checking one guess is easy. Working guesses form one solid block.

for guess in [4, 6, 8, 10]:
    print(guess, guess >= 8)

The template

Halve the result range with the check. The loop ends on the smallest working guess.

def smallest_working(low, high, works):
    while low < high:
        mid = (low + high) // 2
        if works(mid):
            high = mid
        else:
            low = mid + 1
    return low
print(smallest_working(1, 20, lambda guess: guess >= 8))

Worked problem: reading plan

Find the smallest daily page limit that finishes four chapters in two days. The check counts the days a limit needs.

chapters = [100, 200, 300, 400]
def days_needed(limit):
    days = 1
    total = 0
    for pages in chapters:
        if total + pages > limit:
            days += 1
            total = pages
        else:
            total += pages
    return days
def smallest_limit(low, high):
    while low < high:
        mid = (low + high) // 2
        if days_needed(mid) <= 2:
            high = mid
        else:
            low = mid + 1
    return low
print(smallest_limit(400, 1000))

Example

def smallest_hours(goal):
    def works(hours):
        return 12 * hours >= goal
    low = 0
    high = goal
    while low < high:
        mid = (low + high) // 2
        if works(mid):
            high = mid
        else:
            low = mid + 1
    return low
print(smallest_hours(100))

Key points

  • Guess: one possible result value, checked against the problem rules.
  • Use binary search on the answer when the problem asks for a smallest working value.
  • Write a check that says whether a guess works.
  • Working guesses stay working for bigger guesses, so the working range has one edge.
  • Search the result range, not the input list.
  • Binary search on the answer finds the edge of the working range.

Two machines make 12 items per hour together. The code checks each hour guess against the goal of 100 items. The smallest working guess is 9 hours.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

When does binary search on the answer fit?