Search & scan · pattern 7 of 7

Binary search on the answer

Sometimes the answer is a number in a known range, and any guess can be tested with yes or no. When every guess above a passing one also passes, test the middle guess and drop the half that the result rules out.

Watch it run in the app

When to use it

Use it when there is no sorted list to look in: the answer is a number, a guess can be checked, and the guesses that pass all lie on one side.

It belongs to the search & scan group: Move one or two positions across the input so that nothing is looked at more than a few times.

Watch it work

A van must deliver parcels in the order of the list parcels, which gives their weights, over at most days days. Each day it takes the next parcels in line while their weights together stay within the van's limit. Return the smallest limit that is enough.

Input
parcels = [2, 3, 1, 2, 2]
days = 2

Output
5

The method

The limit is from the heaviest parcel to the weight of them all
Guess the limit in the middle of the range
Test the guess: load parcels in order and count the days
In time: the answer is this limit or a smaller one
Too many days: the answer is a larger limit
One limit remains: that is the answer

The run, one moment at a time

Step 1. A limit below 3 cannot take the heaviest parcel. A limit of 10 takes every parcel in one day. So the answer is from 3 to 10.
```
limit: 3 4 5 6 7 8 9 10  (left at 0, right at 7)
in time?: ? ? ? ? ? ? ? yes
parcels: 2 3 1 2 2
```

Step 2. The middle of 3 to 10 is 6. Guess a limit of 6.

limit: 3 4 5 6 7 8 9 10  (left at 0, mid at 3, right at 7)
in time?: ? ? ? ? ? ? ? yes
parcels: 2 3 1 2 2

Step 3. Test 6: load each day with at most 6. The days carry 6 and 4, so this limit needs 2 days.

limit: 3 4 5 6 7 8 9 10  (left at 0, mid at 3, right at 7)
in time?: ? ? ? ? ? ? ? yes
parcels: 2 3 1 2 2
day: 1 1 1 2 2

Step 4. The van may take 2 days, so a limit of 6 is in time. Every larger limit is in time too, so none of them is the smallest: right moves to 6.
```
limit: 3 4 5 6 7 8 9 10  (left at 0, right at 3)
in time?: ? ? ? yes yes yes yes yes
parcels: 2 3 1 2 2
```

Step 2. The middle of 3 to 6 is 4. Guess a limit of 4.

limit: 3 4 5 6 7 8 9 10  (left at 0, mid at 1, right at 3)
in time?: ? ? ? yes yes yes yes yes
parcels: 2 3 1 2 2

Step 3. Test 4: load each day with at most 4. The days carry 2, 4 and 4, so this limit needs 3 days.

limit: 3 4 5 6 7 8 9 10  (left at 0, mid at 1, right at 3)
in time?: ? ? ? yes yes yes yes yes
parcels: 2 3 1 2 2
day: 1 2 2 3 3

Step 5. The van may take only 2 days, so a limit of 4 is too small. Every smaller limit needs at least as many days, so none of them works: left moves to 5.
```
limit: 3 4 5 6 7 8 9 10  (left at 2, right at 3)
in time?: no no ? yes yes yes yes yes
parcels: 2 3 1 2 2
```

Step 2. Two limits remain, 5 and 6. Their middle rounds down to 5, so mid and left are both there. Guess 5.

limit: 3 4 5 6 7 8 9 10  (both at 2, right at 3)
in time?: no no ? yes yes yes yes yes
parcels: 2 3 1 2 2

Step 3. Test 5: load each day with at most 5. The days carry 5 and 5, so this limit needs 2 days.

limit: 3 4 5 6 7 8 9 10  (both at 2, right at 3)
in time?: no no ? yes yes yes yes yes
parcels: 2 3 1 2 2
day: 1 1 2 2 2

Step 4. The van may take 2 days, so a limit of 5 is in time. Every larger limit is in time too, so none of them is the smallest: right moves to 5.
```
limit: 3 4 5 6 7 8 9 10  (both at 2)
in time?: no no yes yes yes yes yes yes
parcels: 2 3 1 2 2
```

Step 6. Left and right are both 5, so one limit remains. The smallest limit that delivers in 2 days is 5.

limit: 3 4 5 6 7 8 9 10  (both at 2)
in time?: no no yes yes yes yes yes yes
parcels: 2 3 1 2 2

The code

The numbered comments are the steps of the method.

JavaScript

function solve(parcels, days) {
  // 1. The limit is from the heaviest parcel to the weight of them all
  let left = Math.max(...parcels);
  let right = 0;
  for (const parcel of parcels) right += parcel;
  while (left < right) {
    // 2. Guess the limit in the middle of the range
    const mid = Math.floor((left + right) / 2);
    // 3. Test the guess: load parcels in order and count the days
    let need = 1;
    let load = 0;
    for (const parcel of parcels) {
      if (load + parcel > mid) {
        need += 1;
        load = 0;
      }
      load += parcel;
    }
    if (need <= days) {
      // 4. In time: the answer is this limit or a smaller one
      right = mid;
    } else {
      // 5. Too many days: the answer is a larger limit
      left = mid + 1;
    }
  }
  // 6. One limit remains: that is the answer
  return left;
}

Python

def solve(parcels, days):
    # 1. The limit is from the heaviest parcel to the weight of them all
    left = max(parcels)
    right = sum(parcels)
    while left < right:
        # 2. Guess the limit in the middle of the range
        mid = (left + right) // 2
        # 3. Test the guess: load parcels in order and count the days
        need = 1
        load = 0
        for parcel in parcels:
            if load + parcel > mid:
                need += 1
                load = 0
            load += parcel
        if need <= days:
            # 4. In time: the answer is this limit or a smaller one
            right = mid
        else:
            # 5. Too many days: the answer is a larger limit
            left = mid + 1
    # 6. One limit remains: that is the answer
    return left

How to spot it

Asked: The smallest speed, size or limit that is still enough: Smallest that is enough means a line between no and yes. When larger values stay enough, halving the range finds that line.
Asked: The earliest time at which something becomes possible: When what is possible stays possible later, the times are a run of no and then a run of yes. Halving finds the first yes.
Given: A budget to keep: finish within a given number of hours or days: The budget turns a guess into a yes or no question: does this guess stay within it? That question is the test.
Limits: The answer can be as large as 1,000,000,000: Trying every value is a billion tests. Halving needs about 30, so each test can afford a full pass over the input.

Looks like it, but is not

A sorted list is given and you must find a value, or its place, in it. Use Binary search on a sorted range. There you halve positions of the list, and a test is one look at a value. Here you halve possible answers, and a test is a calculation.
You want the shortest or longest run of neighbors that meets a condition. Use Variable sliding window. Guessing a length would work, but it is more than is needed. Two ends that only move forward find the best run in one pass.
You want a smallest count, such as the fewest coins that make an amount. Use Knapsack dynamic programming. Testing a guess, such as 5 coins, is as hard as the whole task, so guessing gains nothing. Build the answer from smaller amounts.

Cost and mistakes

Each guess halves the range, so a million possible limits need about 20 guesses. Each test reads all n parcels once. Together that is written O(n log w) for a range of w limits. Extra space is a few numbers, written O(1).

Watch out

Before you halve, check that the results are in order: if one limit passes, every larger limit must pass too. If yes and no are mixed, halving throws the answer away.
Choose the two ends so that the answer is surely between them. A limit below the heaviest parcel can never work, and the weight of all parcels always does.

In the 150

3 problems of the 150 use it. Naming them gives their method away, so the list is folded.

Show the 3

Koko Eating BananasMedium · Binary Search
Median of Two Sorted ArraysHard · Binary Search
Swim In Rising WaterHard · Advanced Graphs