TechPrep
Searching and orderingReadLabPracticeCheck

Binary search, including on the answer

Halve a search space whose predicate flips once from false to true, whether the space is an array or a range of possible answers.

Capacity To Ship Packages Within D Days. Packages weights must ship in order. Each day the ship carries a contiguous run whose total is at most its capacity. Return the smallest capacity that ships everything within days days.

Signals that point here

The idea

Do not search the array; search the answer. Capacity c either works or not, and if c works so does c + 1. That monotone predicate is all binary search needs.

Use one template and never improvise: lo < hi, mid = (lo + hi) // 2, hi = mid when the predicate holds, lo = mid + 1 when it fails. It returns the first value where the predicate is true, and it cannot loop forever.

def ship_within_days(weights: list[int], days: int) -> int:
    def fits(cap: int) -> bool:
        need, load = 1, 0
        for w in weights:
            if load + w > cap:
                need, load = need + 1, 0
            load += w
        return need <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:                   # first capacity where fits() is True
        mid = (lo + hi) // 2
        if fits(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

Complexity

O(n log S) where S is the sum of weights: log S probes, each a linear fits check. O(1) extra space.

Pitfalls interviewers watch for

Variants worth knowing

Test it like the interviewer will

Step through it: ship_within_days([3, 2, 2, 4, 1, 4], 3)

Each step is recorded from an instrumented copy of the Python above, run when the site was built.

Practice

Written for this site to drill the lesson. Not reported interview questions.

  1. Return the first and last index of target in a sorted array.
  2. Find the minimum eating speed that finishes all piles within h hours.
  3. Find the minimum in a rotated sorted array with no duplicates.

Check yourself

What property must the predicate have?

Monotone: false for every value below the answer, true for every value at or above it.

What does the lo < hi, hi = mid template return?

The first value for which the predicate is true.

Saved in this browser.