Binary Search on the Answer

You have six podcast episodes to catch up on, in order: 40, 25, 60, 30, 45 and 20 minutes long. You want to finish them in 3 days. You only listen to whole episodes, and you never skip ahead. To keep each day short, you set a daily limit. What is the smallest limit that still gets you through in 3 days?

Working out the answer directly is awkward: you would have to try every way of cutting the list into 3 days. But checking a guess is easy. Say the limit is 80 minutes. Fill each day until the next episode would go over 80, then start a new day: 40 + 25, then 60, then 30 + 45, then 20. That is 4 days, so 80 is too small. Checking a guess takes one pass over the list. When an answer is hard to find but easy to check, binary search can do the finding.

#The idea: search the answers, not the array

Line up every possible limit from small to large and ask the same question of each: "can I finish in 3 days with this limit?"

• A limit below 60 can never work, because the 60-minute episode would not fit in any day.
• A limit of 220, the total, always works: you could listen to everything in one day.
• If some limit works, any bigger limit works too. A looser limit never needs more days.

So the answers go no, no, no, …, yes, yes, yes. That is exactly the shape from Binary Search: you want the first "yes". The only difference is that the positions are candidate answers instead of array indexes, and checking one means running the day-count instead of reading a[mid].

Checking all 161 candidates one by one would work, but binary search needs only about log₂ 161, which is 8 checks at most.

#Traced

The template is the lower bound from the last lesson. lo starts at the smallest candidate, 60. hi starts at 220, which is known to be a "yes"; it plays the role that n played before. The day row shows which day each episode lands on for the guess being checked.

lo = max(episodes), hi = sum(episodes)while lo < hi:  mid = lo + (hi - lo) // 2  if daysNeeded(mid) <= 3: hi = mid  else: lo = mid + 1return lo

#The code

Split the code into two parts: a general firstYes search you can reuse for any problem of this kind, and the check that is specific to this one.

// Smallest x in [lo, hi] with isYes(x) true.
// isYes must go no, ..., no, yes, ..., yes, and isYes(hi) must be true.
function firstYes(lo, hi, isYes) {
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (isYes(mid)) hi = mid; // mid works: answer is mid or smaller
    else lo = mid + 1;        // mid fails: answer is bigger
  }
  return lo;
}
 
// Assumes limit >= the longest episode.
function daysNeeded(episodes, limit) {
  let days = 1, today = 0;
  for (const minutes of episodes) {
    if (today + minutes > limit) { days++; today = 0; } // start a new day
    today += minutes;
  }
  return days;
}
 
function smallestDailyLimit(episodes, maxDays) {
  const lo = Math.max(...episodes);
  const hi = episodes.reduce((sum, m) => sum + m, 0);
  return firstYes(lo, hi, (limit) => daysNeeded(episodes, limit) <= maxDays);
}
 
smallestDailyLimit([40, 25, 60, 30, 45, 20], 3); // 90

# Smallest x in [lo, hi] with is_yes(x) true.
# is_yes must go no, ..., no, yes, ..., yes, and is_yes(hi) must be true.
def first_yes(lo, hi, is_yes):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_yes(mid):
            hi = mid      # mid works: answer is mid or smaller
        else:
            lo = mid + 1  # mid fails: answer is bigger
    return lo
 
# Assumes limit >= the longest episode.
def days_needed(episodes, limit):
    days, today = 1, 0
    for minutes in episodes:
        if today + minutes > limit:  # start a new day
            days += 1
            today = 0
        today += minutes
    return days
 
def smallest_daily_limit(episodes, max_days):
    lo, hi = max(episodes), sum(episodes)
    return first_yes(lo, hi, lambda limit: days_needed(episodes, limit) <= max_days)
 
smallest_daily_limit([40, 25, 60, 30, 45, 20], 3)  # 90

#How to spot it

Reach for this pattern when the problem says things like "the smallest speed that…", "the largest size such that…", or "minimise the biggest…". Then make sure three things are true:

1. You can bound the answer. Find a lo that is the smallest possible candidate and a hi that surely works.
2. You can check a guess faster than you can find the answer, often with one greedy pass like daysNeeded.
3. The answers are monotone. If x works, x + 1 works too. Say why out loud before you code.

#When you want the largest value

Some problems flip the direction: the answers go yes, yes, …, no, no, and you want the last yes. Do not write a new template. Search for the first no with the same function, then subtract 1. For example, the integer square root of 30 is the largest x with x × x ≤ 30. The first x where x × x > 30 is 6, so the answer is 5.

// Largest x with x * x <= n, for n >= 0.
function intSqrt(n) {
  // n + 1 is surely a "no": (n + 1)² > n
  return firstYes(0, n + 1, (x) => x * x > n) - 1;
}
 
intSqrt(30); // 5

# Largest x with x * x <= n, for n >= 0.
def int_sqrt(n):
    # n + 1 is surely a "no": (n + 1)² > n
    return first_yes(0, n + 1, lambda x: x * x > n) - 1
 
int_sqrt(30)  # 5

#Common mistakes

#Check yourself

#What to practise next

Before the next module, try the pattern on a new question by hand: with the same episodes, what is the smallest limit for 2 days? (It is 125.) The next module starts with Binary Trees, the shape behind binary search trees, where "throw away half" becomes a data structure.