Binary Search

Binary Search on the Answer

Search the smallest value that satisfies a monotonic feasibility check.

Medium, about 90 minutes to practise.

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

MLR
1
2
3
4
0123

lo = max(weight)=4, hi = sum=10. Feasible(mid) = “can ship in ≤ 2 days?”

lo, hi = min_possible, max_possible

Live template

Line 1 active

1lo, hi = min_possible, max_possible
2while lo < hi:
3 mid = (lo + hi) // 2
4 if feasible(mid): hi = mid
5 else: lo = mid + 1
6return lo

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.

  1. Low = max(nums) = 10 (a bucket must hold the biggest element). High = sum = 32.
  2. Try mid 21: greedy count of subarrays needed if no bucket exceeds 21, need 2 → feasible, try smaller.
  3. Try mid 15: need 3 subarrays → not feasible, raise low.
  4. 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.

All lessons