LESSON 5 · PATTERN GUIDE

Binary Search on Answer

Search the answer range when feasibility changes monotonically as the candidate answer changes.

FIRST, LEARN THE PATTERNInstead of searching an array, binary search a numeric answer. A feasibility check tells you whether a candidate is too small or already sufficient.

The prompt asks for the minimum possible maximum, maximum feasible minimum, or another optimized value with a yes/no feasibility test.

How to approach it

Set valid lower and upper bounds, test the midpoint, and shrink toward the smallest or largest feasible answer.

Watch out for

The hardest part is proving monotonicity and writing a correct feasibility check; bounds and integer rounding matter.

A CLOSER EXPLANATION

First turn the optimization question into a yes/no check: 'Can this capacity finish the job within the deadline?' If a capacity works, every larger capacity also works, creating a monotone boundary. Binary search finds the smallest feasible value; the feasibility check often greedily simulates how work is grouped.

NOW YOU TRY

Practice question

A worker must ship weights [3, 2, 2, 4, 1] in 3 days, preserving order. What is the smallest daily capacity that works?

EXAMPLEweights = [3, 2, 2, 4, 1], days = 3Give your answer before revealing the explanation.

Show a hint

Binary search capacity from the heaviest package to the sum of all packages.

Show an answer

6. Capacity 6 allows [3,2], [2,4], [1]; capacity 5 needs 4 days.

CONNECT IT TO REAL LIFE

Binary Search on Answer at work

A warehouse must ship packages weighing [4, 3, 5, 2] in order within 2 days. What is the smallest truck capacity that can meet the deadline?

Show one possible approach

7. Capacity 7 ships [4,3] on day one and [5,2] on day two. Capacity 6 would need three days because the last two packages total 7.

Practice next

Use these problem IDs to find additional practice for this pattern:

875101141077412831482