π± The phrase that pays
"Split the array into k contiguous parts, minimizing the largest part-sum." Candidate A locks onto "minimize the maximum": feasibility of a candidate answer is monotone, so binary search the answer range [max, sum] with a greedy O(n) check β done in 15 minutes with a traced example. Candidate B suspects DP, starts building a recurrence over (index, parts), and runs out of time mid-table. "Minimize the maximum" / "maximize the minimum" is a two-word flag for search-on-answer. Missing the flag costs the whole round.
π§° What you'll learn
- Classic search β the
left <= rightequality shape - Boundary search β first-true with
left < rightandhi = mid - Rotated arrays β one half is always sorted; test the target against it
- Search on answer β binary searching a monotone predicate over a value range
- Feasibility checks: greedy, O(n) per probe, monotonicity proven aloud
Pattern 1 β Sorted-space binary search: equality and boundaries
Two loop shapes, and mixing them is where off-by-ones breed. Equality
search: while left <= right, mid Β± 1 on both exits, return on hit.
Boundary search: while left < right, feasible β hi = mid (mid might be
the answer), infeasible β lo = mid + 1, return lo. Rotated arrays use
the equality shape plus one extra test: compare nums[left] to nums[mid]
to find which half is sorted, then check the target against that half's
range before discarding the other.
| You see⦠| Think⦠|
|---|---|
| Sorted array, find target or insertion point | Classic equality search |
| "First/last occurrence", "first element β₯ x" | Boundary search on a predicate |
| "Sorted array, rotated at an unknown pivot" | Find the sorted half; discard the other |
| O(log n) demanded on an array problem | Binary search in disguise |
| "Peak element", bitonic shape | Compare mid to mid+1; keep the rising side |
Template β boundary search (first index where predicate is true):
def first_true(lo, hi, ok): # ok: F F F T T T over [lo..hi]
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid # mid works β keep it, search left
else:
lo = mid + 1 # mid fails β discard it
return lo # first True; caller validates empties
Complexity: O(log n) time, O(1) space. The discipline: pick one shape
per problem, define ok precisely, and state the invariant β "everything
left of lo is false, everything right of hi is true." That sentence makes
the terminating state obvious and the off-by-ones checkable.
Drills (easy β hard): Binary Search β Find First and Last Position of Element in Sorted Array (two boundary runs) β Find Minimum in Rotated Sorted Array β Search in Rotated Sorted Array.
Pattern 2 β Search on answer: binary search where nothing is sorted
The upgrade. If a candidate answer's feasibility is monotone β false below the optimum, true at and above it β the answer space is sorted, and binary search applies to any space with that shape: harvest rates, shipping capacities, subarray-sum ceilings, even the kth-smallest value in a matrix with sorted rows and columns (count elements β€ mid in O(n) with a staircase walk from the bottom-left). The feasibility check is usually greedy and O(n); total cost is O(n log(hi β lo)).
| You see⦠| Think⦠|
|---|---|
| "Minimize the maximum / maximize the minimum" | Search on answer |
| "Minimum speed/capacity/rate to finish within a limit" | Monotone feasibility over a value range |
| Brute force would be O(range Γ n) | Compress the range factor to log |
| kth smallest with sorted rows/columns | Binary search the value; count β€ mid fast |
| "Can we do X within budget Y?" | Feasibility predicate + binary search |
Template β minimize the maximum split:
def minimize_max_split(nums, k):
def feasible(cap): # monotone in cap
chunks, running = 1, 0
for x in nums:
if running + x > cap:
chunks, running = chunks + 1, x
else:
running += x
return chunks <= k
lo, hi = max(nums), sum(nums) # tight bounds β justify aloud
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid): hi = mid
else: lo = mid + 1
return lo
Complexity: O(n log(hi β lo)) time, O(1) extra space. The bounds are
part of the answer: lo = max(nums) because no split can dodge the largest
element, hi = sum(nums) because one chunk is always legal. Deriving those
two lines aloud is worth more than the binary search itself.
Drills (easy β hard): Koko Eating Bananas (min speed) β Capacity to Ship Packages Within D Days (min weight) β Split Array Largest Sum (the template, verbatim) β Kth Smallest Element in a Sorted Matrix (count-based feasibility).
π€ Coding drill: run it
You are a staff engineer running a timed coding drill at a top tech company. Run one drill
drill with me on BINARY SEARCH, including search-on-answer problems
where the input is not sorted but a feasibility predicate is monotone.
1. Pick ONE problem that maps to these patterns at senior difficulty.
State it concisely: setup, input, output, one worked example, one
constraint worth noticing. Do not name the pattern it uses.
2. Enforce a 30-minute timer. Warn me at 5 minutes left; stop me at zero.
3. Ask which language I'm using and hold me to it.
4. Hints only when I explicitly ask, one rung at a time, never code:
(a) nudge β restate the constraint or point at a suspicious example;
(b) direction β name the family of approach, not the algorithm;
(c) structure β outline the algorithm's steps in words.
5. Drill like a senior loop: make me restate the problem, state my
complexity unprompted, and trace one example before I call it done.
6. When time is up or I say done, grade 1-5 each: correctness, complexity
analysis, communication, edge cases β one line of evidence per score,
then the single highest-leverage improvement.
Start with the problem statement. No preamble.
β You own it when
- You keep the two loop shapes separate and can say when each applies
- You state the invariant ("left of lo false, right of hi true") before coding
- Rotated arrays: the sorted-half test is a reflex
- "Minimize the maximum" triggers search-on-answer in under a minute
- You derive lo/hi bounds aloud instead of defaulting to 0 and infinity
- You state O(n log(range)) and name where each factor comes from
π Jargon
| Term | What it means |
|---|---|
| Search space | The candidates still possible β your pointers bound it |
| Boundary search | Finding the first/last index where a predicate flips |
Predicate (ok) |
A yes/no feasibility test; binary search needs it monotone |
| Monotone | Once true, stays true (or vice versa) as the candidate grows β the precondition |
| Search on answer | Binary searching candidate values rather than array positions |
| Feasibility check | The greedy O(n) probe deciding which half survives |
π When it goes wrong
- Blanking. Ask: is any quantity here monotone? If yes, you can binary search it even when the array is chaos. Saying that aloud is half the answer.
- Wrong shape. Mixing
left <= rightwithhi = midloops forever or skips the answer. Pick the shape, write the invariant next to it. - Off-by-one on mid.
hi = midpairs withwhile lo < hiand nomid Β± 1;while left <= rightpairs withmid Β± 1on both branches. The pairs go together β write them as a pair. - Non-monotone predicate. If
okisn't monotone, binary search returns garbage silently. Verify the monotonicity claim out loud before coding. - Bounds too loose.
lo = 0, hi = 10**18works but signals guesswork. Tight bounds (max,sum) show you understood the problem's physics. - Skipping the trace. Binary search bugs are invisible until you trace one 5-element example by hand. Do it before saying done.