1. Concept library
  2. Data Structures & Algorithms
  3. Module 8: Binary search

Concept

Search on the answer

When a yes-or-no question is monotonic in some number, binary search over that number finds the smallest value that works. It solves "minimum capacity", "earliest day" and "maximum size" problems without searching an array.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain what makes a yes-or-no question monotonic
  2. Solve a minimum-capacity problem by binary searching over the answer
  3. Spot bounds that exclude the real answer

In practice

A few lines that show Search on the answer doing its job.

Python
def min_ship_capacity(weights, days):
    def feasible(capacity):
        used, load = 1, 0
        for w in weights:
            if load + w > capacity:
                used, load = used + 1, 0
            load += w
        return used <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid): hi = mid
        else: lo = mid + 1
    return lo

The common mistake

Watch for

Picking bounds that exclude the answer, such as lo = 0 for a capacity that must carry the heaviest item. The search then returns a value the check never approved.

What to know first

Your roadmap puts these before Search on the answer, unless you already know them.

How it stays learned

Once a session shows you understand Search on the answer, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled
Previous in the module← Search on sorted arrays
Next in the moduleBoundary conditions →