1Understand
The idea
When the question is "what is the smallest value that works?" and working is monotonic (if x works, every larger x works too), binary search over the possible answers. Each guess costs one feasibility check; usually a greedy O(n) pass, for O(n log range) in total.
Intuition
When the question is "what is the smallest value that works?" and working is monotonic (if x works, every larger x works too), binary search over the possible answers, not over indices in the array.
Each mid guess runs a feasibility check; usually a greedy O(n) pass. The search range is often [min(capacity), sum(...)] or [0, max(span)].
The hard part is proving monotonicity and writing a correct ok(x) predicate; the binary search shell is standard.
What you will be able to do
- Write a monotonic feasibility check
- Choose the answer range
When to use it
- Minimise the maximum / maximise the minimum
- "Smallest capacity / speed / time such that…"
- A check(x) that is false…false, true…true
2See it
Walkthrough
Minimize capacity to ship packages
weights = [1, 2, 3, 4], days = 2, binary search the capacity.
1 / 4
lo = max(weight)=4, hi = sum=10. Feasible(mid) = “can ship in ≤ 2 days?”
Live template
Line 1 active
Complexity: time O(n log R), space O(1)
Total time O(n log R) where R is the answer range width. Space O(1) beyond input. Prefer this over DP O(n²m) when constraints make the log factor attractive and monotonicity holds.
Read the walkthrough as text
Split array largest sum / allocate mailboxes. Classic: split nums = [7,2,5,10,8] into m = 2 subarrays to minimise the largest subarray sum.
- Low =
max(nums) = 10(a bucket must hold the biggest element). High =sum = 32. - Try mid
21: greedy count of subarrays needed if no bucket exceeds 21, need 2 → feasible, try smaller. - Try mid
15: need 3 subarrays → not feasible, raise low. - Converge to
18([7,2,5]and[10,8]).
Feasibility is "can I finish with at most m pieces if each piece sums to ≤ mid?".
3Recognise it
Kinds of problems (8)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Minimum speed / rate (Koko)
Example. Minimum eating speed to finish piles in h hours.
How. Binary search speed; feasible(s) = total ceil(pile/s) ≤ h.
Minimum capacity (ship packages)
Example. Smallest ship capacity that delivers all packages in D days.
How. Binary search capacity; greedy check packs consecutive weights within cap per day.
Split array to minimise the largest sum
Example. Split into m subarrays; minimise maximum subarray sum.
How. Binary search max sum; greedy count pieces needed if no piece exceeds mid.
Maximise the minimum distance
Example. Place k balls in sorted positions; maximise minimum gap.
How. Binary search distance d; greedy place next item ≥ d apart, count how many fit.
Integer square root
Example. Floor of √n without math.sqrt.
How. Binary search x in [0, n]; largest x with x*x ≤ n.
Partition point across two sorted arrays (median of two arrays)
Example. Median of two sorted arrays in O(log min(n,m)).
How. Binary search cut in smaller array so left halves match partition of total length.
Minimise the maximum with a greedy check
Example. Split into k parts minimising the largest part sum.
How. Answer search on max sum; validation is one linear greedy partition count.
Largest k that keeps a property
Example. Maximum number of operations before a limit breaks.
How. Binary search k; check(k) true for small k and false after, search last true.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Non-monotonic check
Why it happens. Feasibility flips back and forth as x increases, binary search does not apply.
How it fails. check(x) true for x=3, false for x=4, true again for x=5, binary search returns wrong answer.
Fix. Prove false…false, true…true (or the maximize variant); otherwise search the discrete structure directly.
Wrong search range
Why it happens. Initial lo/hi excludes the optimum.
How it fails. Capacities from 1..sum(weights) but hi = max(weights), feasible answer needs larger cap.
Fix. Set bounds from problem limits: min possible, max possible (often sum or max element).
Keeps the wrong side
Why it happens. Minimise answer but you move lo when feasible (finding max instead).
How it fails. Ship packages: feasible(mid) → lo = mid + 1 returns largest capacity, not smallest.
Fix. Minimise: if feasible(mid): hi = mid else lo = mid + 1. Maximise: invert the branch.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.