You understand binary search after you see the solution. This notebook fixes the other direction: looking at an unfamiliar problem and reconstructing the search from first principles.
Binary search is not "a sorted array + two pointers." It is one idea wearing many costumes:
There is a point where the answer flips from NO to YES, and testing the middle tells me which side that flip is on. Every half I throw away, I throw away because I have proven the flip cannot be there.
So the real question is never "how do I write the loop." It is:
"What fact lets me confidently eliminate half the remaining possibilities?"
If you can name that fact, the code writes itself. If you cannot, no template will save you. The eight questions below turn that fact into working code — run them in order on any candidate problem.
[lo, hi]? A value domain? Name it explicitly.
mid mean? Say it in words: "mid is a candidate eating speed," "mid
is an index," "mid is a possible k-th value." If you can't finish the sentence, you're not ready to code.mid works, which half is safe to discard? Prove it from the monotonic
property, not from intuition.mid fails, which half is safe to discard? Same — prove it.lo < hi converges the two pointers onto the
boundary; lo <= hi is for "found it, return now" exact-match searches.lo (the boundary), a stored candidate ans, or
an index. Know this before the loop, not after.You reach for the code (question 7 and 8) before answering questions 1–4. The costume changes every problem; the four questions underneath never do. Train the questions, not the loops.
Your draft mixed "find peak," "rotated," and "classic" into one bucket, and split lower/upper bound off on their own. I regrouped around reasoning technique, not surface features. Boundary search (lower/upper bound) is not its own pattern — it is the engine, so it opens the notebook and every later pattern reuses it. Peak and rotated searches are separated from classic search because their monotonic property is a local shape, not sorted order — a genuinely different mental move. The result is six patterns, each teaching something the others don't.
Almost every binary search you will write in an interview is secretly the same search: find the leftmost position where a monotonic predicate becomes true. Write it once, understand it deeply, and reuse it everywhere.
Picture the search space laid flat with the predicate evaluated at each spot. Monotonic means it looks like
this — never like F T F T:
The whole game: keep a window [lo, hi) that is guaranteed to contain the boundary. Test
the middle. Because the strip is monotonic, one answer at mid proves an entire half is safe to
drop.
The boundary is at mid or to its left. Everything right of mid
is also true and can't be the first true. Keep mid: hi = mid.
The boundary is strictly to the right. mid itself is false, so it can't be
the answer. Discard it: lo = mid + 1.
Predicate strip below. Watch how lo/hi
squeeze onto the first TRUE, and how each step provably deletes a half. Reshuffle to see the boundary move.
Ninety percent of interview binary searches are one of these two. Learn why the boundaries differ and you never guess again.
A · First TRUE (lower bound) — the workhorse
int lo = 0, hi = n; // [lo, hi) — hi is ONE PAST the end
while (lo < hi) { // stop when window is empty
int mid = lo + (hi - lo) / 2;
if (check(mid)) hi = mid; // mid may be the answer, keep it
else lo = mid + 1; // mid fails, drop it
}
return lo; // first true index (== n if none)B · Exact match — only when you want equality
int lo = 0, hi = n - 1; // [lo, hi] — both ends inclusive
while (lo <= hi) { // stop when they cross
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // not presentTemplate A converges onto a boundary that always exists, so it never needs to
"return from inside the loop" — it narrows [lo,hi) until lo == hi lands exactly on
the first true. It uses hi = mid (not mid-1) precisely because mid could be
the answer and must survive.
Template B is hunting for a specific value that may not exist, so it can quit early
with return mid, and safely does mid±1 everywhere because a matched mid is returned,
not discarded.
Default to A. Boundary search subsumes "first occurrence," "last occurrence," "insertion
point," "first ≥ target," "first > target," and every binary-search-on-answer problem. You reshape
check; the skeleton never moves.
| You want… | Define check(i) as | Answer is |
|---|---|---|
First index with a[i] ≥ target (lower bound) |
a[i] >= target |
lo |
First index with a[i] > target (upper bound) |
a[i] > target |
lo |
Last index with a[i] < target |
lower bound of target, then | lo - 1 |
Last index with a[i] <= target |
upper bound of target, then | lo - 1 |
Count of elements < target |
lower bound of target | lo |
Don't memorize four functions named lower_bound / upper_bound. Memorize one move:
"find first TRUE, then adjust by ±1 or read the count." Everything to the left of
lo is false; everything from lo on is true. Last-anything = lo - 1.
The costume you already know: a sorted array, and you want a value, a position, or a boundary
inside it. The monotonic property is handed to you for free — sorted means "everything left of the
answer is smaller, everything right is bigger." You binary search over indices;
mid is an index; you discard the half that provably can't contain what you're looking for.
The trap here is thinking this pattern is only "find target." Ninety percent of interview value is the boundary flavor: first occurrence, last occurrence, insertion point, first element ≥ x. All of those are Template A with a one-line predicate. Reach for exact-match (Template B) only when the literal answer is "does this value exist, and where."
The word "sorted" appears (or you can cheaply sort), and you want a single position/value. If the array is sorted but you're optimizing a quantity, you're probably in Pattern 3, not here.
a[mid]=12 < 16, so 16 (if present) is strictly right →
indices 0–3 vanish in one step.For exact match use Template B from the section above. For every boundary flavor, use Template A. Below: insertion position, which is just "first index whose value is ≥ target."
// Search Insert Position == lower bound of target
int lo = 0, hi = nums.length; // [lo, hi)
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] >= target) hi = mid; // candidate, keep
else lo = mid + 1;
}
return lo; // where target belongs (0..n)Run the drill: (1) search space = indices [0, n]. (2) mid = an index. (3) monotonic
property = "nums[i] ≥ target" flips false→true exactly once because sorted. (4) I want the
first true → Template A. (5) mid true → answer is mid-or-left, hi=mid. (6) mid false →
answer is strictly right, lo=mid+1. (7) stop at lo==hi. (8) return lo.
Notice you never touched a single line of code from memory.
Array [1, 3, 5, 7, 9, 11], exact-match (Template B),
lo=0 hi=5.
lo=0, hi=5 → mid=2. a[2]=5 < 9. Target is
right of mid. Discard 0–2 → lo=3.lo=3, hi=5 → mid=4. a[4]=9 == 9. Match.
Return 4.Two comparisons for six elements. With a million elements it would be ~20. That's the whole reason this exists.
Why it matters: The pure skeleton. Write it until closed-interval exact match is muscle memory, then never write it from scratch again — everything else is a predicate swap.
[lo,hi] or half-open [lo,hi)? Pick one and stay consistent.Why it matters: Your first taste that "not found" is not failure — it's a position. This is lower bound in disguise and the gateway to boundary thinking.
lo=0, hi=n (yes, n, not n−1 — the answer can be
"past the end").nums[mid] >= target. Return
lo. This is literally lower bound.
Why it matters: The predicate is given to you as an API call, not an array comparison. Forces you to see binary search as "find first TRUE" with zero sorted array in sight.
isBadVersion(i).)check(i) = isBadVersion(i).
lo=1, hi=n. mid = a version number.mid = lo + (hi-lo)/2, never
(lo+hi)/2 — n can be ~2³¹.
Why it matters: Proves one search isn't special — you run boundary search twice (lower bound of target, upper bound of target) and read the range between. The clearest "duplicates need boundaries" lesson.
[first, last] of target."a[i] >= target. Right =
(first index with a[i] > target) − 1.left > right or
a[left] != target, target is absent → return [-1,-1].
Why it matters: Strict upper bound with a wrap-around twist. Tiny change to the
predicate (> not >=) and a modulo at the end — cements that the predicate, not
the skeleton, carries the meaning.
letters[i] > target.
lo=0, hi=n. Answer index might be n.
letters[lo % n].Why it matters: Teaches that "search space" is a choice, not a given. Treat the
matrix as one flattened sorted array of length m·n and map an index back with / and
%. (Its cousin 240 has a weaker guarantee — see Pattern 2.)
k to (row, col)?
(row=k/n, col=k%n.)lo=0, hi=m*n-1, exact match (Template B).matrix[mid/n][mid%n].Here the array is not globally sorted, yet a local shape is still monotonic enough to
throw away a half. This is the pattern people force into "classic" search and then get lost. It deserves its own
head-space because the discard rule no longer comes from comparing a[mid] to a target — it comes
from comparing a[mid] to a neighbor or an endpoint to figure out which half is
"well-behaved."
Two shapes cover almost everything:
a[mid] with
a[mid+1]. Uphill? a peak is right. Downhill? a peak is at mid or left. You are binary searching
without any target at all.
mid, one side is
still perfectly sorted. Detect which side, check if the target lives in that clean side's range, and
recurse on the appropriate half."Rotated," "mountain," "peak," "first increases then decreases," or a sorted array that's been shifted. Also: you have no target but a structural landmark to find. That "no target, yet still binary-searchable" feeling is the tell.
a[lo]=6 <= a[mid]=9 → left half [0..3] is sorted. Is target in [6,9]?
If yes search left, else search right.Peak (no target, compare to neighbor)
int lo = 0, hi = n - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] < a[mid + 1])
lo = mid + 1; // uphill → peak is right
else
hi = mid; // downhill → peak here or left
}
return lo; // a peak indexRotated search (find target)
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
if (a[lo] <= a[mid]) { // left sorted
if (a[lo]<=target && target<a[mid]) hi=mid-1;
else lo=mid+1;
} else { // right sorted
if (a[mid]<target && target<=a[hi]) lo=mid+1;
else hi=mid-1;
}
}
return -1;Peak: (3) monotonic property = "am I on the rising or falling slope?" — that flips once. (4) first index where you start falling = the peak → first-true style. Rotated: the monotonic fact isn't the array, it's "at any mid, exactly one side is sorted." Once you trust that, the check is just "is target inside the clean side's known range?" — if yes go there, otherwise the answer must be in the messy side.
A peak is bigger than both neighbors; edges count as −∞ outside. Climb toward the higher neighbor and a peak is guaranteed.
lo=0, hi=6 → mid=3, a[3]=3 < a[4]=5. Uphill. A peak must be right → lo=4.lo=4, hi=6 → mid=5, a[5]=6 > a[6]=4. Downhill. Peak is here or left → hi=5.lo=4, hi=5 → mid=4, a[4]=5 < a[5]=6. Uphill → lo=5. Now lo==hi.Return index 5. No target, no sorted array — the slope direction was the monotonic signal all along.
lo=0, hi=6 → mid=3, a[3]=9. a[lo]=6 <= 9 → left
sorted [6..9]. Is 2 in [6,9)? No. Discard left → lo=4.lo=4, hi=6 → mid=5, a[5]=2 == target. Return
5.The move that unlocks it: identify the sorted side first, then ask if the target fits in its known range.
Why it matters: The purest "binary search with no target." Once you can solve this, you've internalized that monotonicity — not sortedness — is the real precondition.
[0, n-1]. Compare a[mid] vs
a[mid+1].
Why it matters: Same slope logic as 162 but with a guaranteed single peak. Good for confirming the template transfers when the problem "shape" is stated explicitly as a mountain.
Why it matters: Finds the rotation pivot (the min) by comparing
a[mid] to a[hi]. Teaches the "compare to an endpoint, not a target" reflex that
makes rotated search click.
a[lo] or a[hi]? Why is a[hi] safer?[lo,hi] with hi=n-1; loop while
lo<hi.
a[mid] > a[hi], min is strictly right →
lo=mid+1. Else hi=mid. Never mid-1 here — mid could be the min.
Why it matters: The canonical rotated search and a top-tier interview frequency problem. Combines pivot logic with target containment — the synthesis of everything in this pattern.
a[lo] <= a[mid] ⇒ left half sorted; otherwise
right half sorted.Why it matters: Adds duplicates, which can break the "which side is sorted" test
when a[lo]==a[mid]==a[hi]. Teaches the graceful degradation to O(n) worst case and why duplicates
poison monotonicity.
a[lo]==a[mid]==a[hi] you can't tell which
side is sorted — shrink both ends (lo++, hi--) and retry.Why it matters: A structural cousin. Rows and columns sorted, but not globally — so flattening (74) fails. The O(m+n) staircase from the top-right corner is a "monotone elimination" that isn't literally binary search, and knowing the difference is the lesson.
The mental leap that makes this hard: there is no array to search. You invent the search
space. The array in the problem is just data; the thing you binary search is a range of possible
answers — a speed, a capacity, a divisor, a maximum-allowed-sum. For each candidate answer
mid, you ask a yes/no question — feasible(mid)? — and that question is usually a
simple O(n) loop.
Why it works: as the candidate answer grows, feasibility flips once. Bigger eating speed → strictly easier to finish in time. Bigger ship capacity → strictly easier to ship in D days. That single-flip guarantee is your F…F T…T strip. You are back to "find first true," except the strip is a made-up range of answers.
feasible(k) = "can I finish at speed k?" We want
the smallest feasible = 4."Minimize the maximum," "maximize the minimum," "smallest/largest X such that a condition holds," or "the answer is a number between X and Y, and if K works then everything bigger (or smaller) than K also works." The instant you can say "if K works, K±1 also works," you are here.
Ninety percent of these problems are trivial once you have feasible(mid). Design it in
three moves:
mid and simulate. "Suppose the allowed value is exactly
mid. Walk the data once and compute what that forces."
≤ H, ≤ D, ≥ m).
mid up, does the computed number
move the right way?" If yes, you have your F…F T…T (or T…T F…F).Minimum feasible (F…F T…T) — Koko, ship, divisor, split
int lo = minCand, hi = maxCand;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (feasible(mid)) hi = mid; // works → try smaller
else lo = mid + 1;
}
return lo; // smallest value that worksMaximum feasible (T…T F…F) — magnetic force, max-min
int lo = minCand, hi = maxCand;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2; // upper mid!
if (feasible(mid)) lo = mid; // works → try bigger
else hi = mid - 1;
}
return lo; // largest value that worksIn the max feasible template you MUST bias mid upward with +1:
mid = lo + (hi - lo + 1) / 2. Otherwise when hi = lo + 1 and
feasible(mid) is true, lo = mid leaves lo unchanged → forever. The
rule: if a branch does lo = mid, round mid up.
(1) Search space = the range of possible answers, e.g. Koko speed [1, max(pile)]. (2)
mid = a concrete candidate answer. (3) monotonic property = feasibility flips once. (4) most of
these want the minimum feasible answer → min template. (5) feasible(mid) true → smaller might also
work, keep mid (hi=mid). (6) false → mid too small, lo=mid+1. (7) stop at
lo==hi. (8) return lo. The only per-problem work is bounds + feasible.
lo = the smallest answer that could conceivably be legal (speed 1, capacity = largest single item, divisor 1). hi = an answer guaranteed feasible (capacity = sum of all items, speed = biggest pile, divisor = max element). Set hi to something you can prove is always feasible — then the search can only shrink toward the true minimum.
feasible(k) = sum of ceil(pile/k) ≤ 8. Search speed in
[1, 11]. Want the minimum.
lo=1, hi=11 → mid=6. Hours = 1+1+2+2 = 6 ≤ 8 → feasible. Try slower: hi=6.lo=1, hi=6 → mid=3. Hours = 1+2+3+4 = 10 > 8 → infeasible. Too slow: lo=4.lo=4, hi=6 → mid=5. Hours = 1+2+2+3 = 8 ≤ 8 → feasible. hi=5.lo=4, hi=5 → mid=4. Hours = 1+2+2+3 = 8 ≤ 8 → feasible. hi=4. Now lo==hi==4.Answer = 4 bananas/hour. Notice we never sorted the piles — the answer range was the sorted, monotonic thing.
Why it matters: The gentlest "answer is a number, not an index." Search
k in [0, x]; feasible = k*k <= x; you want the largest feasible. A
clean first max-feasible search.
k*k overflow — use long.Why it matters: The archetype. If you can derive this cold — bounds, feasibility, direction, return — you can derive most of the pattern.
[1, max(piles)]; mid = a candidate speed.feasible(k)=Σ ceil(pile/k) ≤ H. Faster is always
feasible → smallest true. Min-feasible template.Why it matters: Same shape as Koko but the feasibility loop is a greedy fill
(order matters, can't reorder packages). Trains you to write a slightly richer feasible without
changing the skeleton.
lo=max(w), hi=sum(w).feasible(cap) greedily packs left-to-right,
counts days, checks ≤ D. Min-feasible.Why it matters: Near-identical to Koko with a different feasible.
Solving both back-to-back proves to yourself the skeleton is fixed and only the check changes.
feasible(d)=Σ ceil(num/d) ≤ threshold; bigger
divisor → smaller sum → min-feasible.Why it matters: The candidate is "days," and feasibility requires scanning for
consecutive bloomed flowers. First problem where feasible needs a run-length idea — a
step up in check design.
[min(bloom), max(bloom)].feasible(day) counts bouquets from maximal runs
of flowers with bloom[i] ≤ day; check ≥ m.Why it matters: The mirror image — you maximize the minimum gap. Forces
the max-feasible template with its upper-mid trap, so it locks in why lo=mid needs
mid rounded up.
[1, max-min] after sorting positions.feasible(gap) greedily places balls ≥ gap apart,
counts placed ≥ m. Use the upper-mid max template.Why it matters: The "minimize the maximum" flagship. Recognizing that the elusive answer (the largest subarray sum) is itself the thing to binary search — with a greedy feasibility count of splits — is the exact reasoning jump interviewers probe.
lo=max(nums), hi=sum(nums); mid = a cap.feasible(cap) greedily counts how many pieces
you need to keep every piece ≤ cap; feasible if pieces ≤ k. Min-feasible. (Identical skeleton to Capacity to
Ship / Magnetic Force — this family is one idea.)A close relative of Pattern 3, but the twist earns it a separate slot: the candidate mid is a
possible value of the answer, and feasible(mid) is a counting
question — "how many things in my data are ≤ mid?" This is how you binary search for a k-th smallest
something without ever materializing all the candidates (there might be n² of them).
The monotonic fact: count(≤ v) is non-decreasing in v. So "is
count(≤ mid) ≥ k?" is a clean F…F T…T strip over the value range. The smallest v where
that count reaches k is exactly the k-th smallest value — and it's guaranteed to be a real element
because the count only jumps at real values.
"K-th smallest / largest" over pairs, products, distances, or a matrix, where listing all candidates is too expensive, but counting how many are ≤ v is cheap (often via sorting + two pointers or per-row binary search). Also "median of …" (median = the (n/2)-th smallest).
count(≤ v). Want k=3rd smallest
→ first v where count ≥ 3, i.e. v=3.int lo = minValue, hi = maxValue; // value range, not indices
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (countLessEqual(mid) >= k) hi = mid; // enough → shrink
else lo = mid + 1;
}
return lo; // the k-th smallest valuelo is guaranteed to be a real element
Even though we search over a continuous range of values, the count only increases when
mid crosses an actual data value. The convergence point is therefore always a value that truly
exists — you never return a "gap" number. This is the subtle correctness argument worth stating in an
interview.
(1) Search space = the value range [min, max] the answer could take. (2) mid = a
candidate value. (3) monotonic property = count(≤ mid) only grows. (4) want the first
value whose count reaches k → min-feasible. (5)/(6) count ≥ k → answer is mid-or-smaller; count < k →
strictly bigger. (8) return lo. The whole difficulty is writing an efficient
countLessEqual.
Why it matters: The most surprising member — no sorting, no explicit search array. You binary search the value 1…n and count how many elements are ≤ mid. If the count exceeds mid, a duplicate hides at or below mid. A perfect "aha, the answer space is the numbers themselves."
count(≤ mid) > mid tell me by pigeonhole?lo=1, hi=n; mid = a candidate value.mid elements are ≤
mid, the duplicate is in [lo, mid] → hi=mid; else
lo=mid+1.
Why it matters: The clean template case. Search values in
[matrix[0][0], matrix[n-1][n-1]]; count elements ≤ mid in O(n) using the row/column sortedness
(staircase from bottom-left). Cements "binary search values, count with a cheap pass."
Why it matters: There are O(n²) pair distances — you can't list them. Sort, then binary search the distance value, counting pairs within distance mid via a sliding window. The definitive "count, don't enumerate" problem.
lo=0, hi=max-min.count(≤ mid) with a two-pointer window over the
sorted array; find smallest distance with count ≥ k.Why it matters: An implicit matrix you never build. Count values ≤ mid in the
m×n table by summing min(mid/i, n) per row. Reinforces that "the data" can be a formula, not
memory.
min(mid/i, n) entries ≤ mid;
sum across rows, min-feasible on count ≥ k.Here binary search is not the algorithm — it's a subroutine that keeps some auxiliary structure sorted so each update is O(log n) instead of O(n). The final answer is produced by the surrounding algorithm; binary search just does the fast lookup inside the loop. This is why LIS drops from O(n²) to O(n log n).
The signature: you're maintaining a container that stays sorted by construction, and on each step you need "where does this new element belong / what's the first thing ≥ it." That question is a lower/upper bound — the boundary search from Pattern 1, used as a tool.
You have an O(n²) DP or scan, and inside the inner loop you repeatedly search a monotone/sorted helper array. Whenever you catch yourself doing a linear scan over something that happens to stay sorted, a boundary search replaces it.
tails[i] = the smallest possible tail of any increasing subsequence of length i+1.
It's always sorted. Each new number replaces the first tail ≥ it (or extends the array).
int[] tails = new int[n];
int len = 0;
for (int x : nums) {
// lower bound: first index with tails[i] >= x
int lo = 0, hi = len;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (tails[mid] >= x) hi = mid;
else lo = mid + 1;
}
tails[lo] = x; // replace or append
if (lo == len) len++; // x extended the LIS
}
return len;tails is provably strictly increasing at all times (a shorter subsequence
always ends smaller), so lower bound is well-defined. Unlike Patterns 1–4, the binary search does
not locate the final answer — len does. The search only maintains the structure
that makes len cheap to update. Note: tails is not a real LIS, only its
length is correct.
Start from the O(n²) DP, spot the repeated inner scan, and ask "is the thing I'm scanning sorted?" If yes, the scan becomes a boundary search. For LIS specifically: use lower bound (first ≥ x) for strictly-increasing; switch to upper bound (first > x) if the problem allows equal elements (non-decreasing). That one predicate swap is the entire difference.
x=10: tails empty → append. tails = [10]x=9: first tail ≥ 9 is index 0 → replace. tails =
[9]x=2: first ≥ 2 is index 0 → replace. tails = [2]
x=5: none ≥ 5 → append. tails = [2, 5]x=3: first ≥ 3 is index 1 (value 5) → replace. tails = [2,
3]x=7: none ≥ 7 → append. tails = [2, 3, 7]x=18: none ≥ 18 → append. tails = [2, 3, 7, 18]
x=8: first ≥ 8 is index 3 (value 18) → replace. tails =
[2, 3, 7, 8]Length = 4. Every "replace" was a
lower-bound search. The tails array [2,3,7,8] isn't the actual subsequence — but its
length is the answer, computed in n·log n.
Why it matters: The definitive "binary search as a helper." Learn the patience-sorting / tails trick here and you'll recognize the shape everywhere.
tails[i] mean, and why is it always sorted?Why it matters: LIS in disguise across two dimensions. The clever sort (width ascending, height descending on ties) reduces it to a 1-D LIS on heights — then reuse the exact helper from 300. Rewards pattern recognition over new machinery.
The most specialized and the hardest to derive cold, so treat it as a named technique: you binary search where to cut one array so that the two arrays, split into a combined "left group" and "right group," satisfy a balance condition. You don't search for a value or a feasibility threshold — you search for a partition point.
For the median of two sorted arrays: cut A at i and B at j so that the left halves
together hold exactly half the elements, and every left element ≤ every right element. Fixing
i forces j (their sizes must sum to half), so it's a 1-D search on i —
over the smaller array to stay O(log min(m,n)).
Two (or more) sorted arrays, and you need a global order statistic — median, k-th smallest across both — in logarithmic time. The words "two sorted arrays" + "median" + "O(log)" is almost always this exact problem.
A: a0 a1 | a2 a3 L1 = a1 R1 = a2
B: b0 | b1 b2 b3 L2 = b0 R2 = b1
Correct cut ⇔ L1 <= R2 AND L2 <= R1
too far right in A? a1 > b1 → move A's cut left
too far left in A? b0 > a2 → move A's cut right// ensure A is the smaller array; total = m + n
int lo = 0, hi = m; // cut position in A: 0..m
while (lo <= hi) {
int i = (lo + hi) / 2; // elems from A on the left
int j = (total + 1) / 2 - i; // elems from B on the left
int L1 = i==0? MIN : A[i-1], R1 = i==m? MAX : A[i];
int L2 = j==0? MIN : B[j-1], R2 = j==n? MAX : B[j];
if (L1 <= R2 && L2 <= R1) { // balanced → answer at the border
if (total % 2 == 1) return max(L1, L2);
return (max(L1,L2) + min(R1,R2)) / 2.0;
} else if (L1 > R2) hi = i - 1; // A's cut too far right
else lo = i + 1; // A's cut too far left
}Search the smaller array (bounds correctness + speed). Use ±∞ sentinels for empty
sides so border comparisons never index out of bounds. And j is fully determined by
i — you never search two things.
(1) Search space = cut positions 0..m in the smaller array. (2) mid/i =
"how many of A's elements go left." (3) monotonic property = as i grows, L1 rises and
R1 rises, so the two imbalance conditions each flip once. (4) you want the unique balanced cut. (5)
L1 > R2 → too many big A-elements on the left → move left. (6) L2 > R1 → move
right. (7) exact-match style loop. (8) return the median assembled from the four border values.
A is smaller, search i in [0,2]. Need 3 elements on the left
overall: j = 3 - i.
lo=0, hi=2 → i=1, j=2. L1=A[0]=1, R1=A[1]=3, L2=B[1]=3, R2=B[2]=5. Check
L1≤R2 (1≤5) ✓ and L2≤R1 (3≤3) ✓. Balanced!
(max(L1,L2)+min(R1,R2))/2 = (3+3)/2. Median = 3.0.
One iteration found the cut. The search never merged the arrays — it only hunted the balance point, in O(log min(m,n)).
Why it matters: The canonical partition search and a classic hard interview problem. Teaches "binary search the cut, not the value," plus disciplined edge handling with sentinels — a reasoning move no other pattern gives you.
maxLeftA ≤ minRightB and
maxLeftB ≤ minRightA. Use ±∞ for empty sides.
Run a new problem through this top-down. The first "yes" that fits tells you the pattern and the template.
Sorted + find something → P1. Rotated/peak → P2. "Min the max / max the min / smallest valid" → P3. "K-th smallest of a huge candidate set" → P4. "Speed up an O(n²) with a sorted helper" → P5. "Median of two sorted arrays" → P6.
Every one of these is a boundary or termination bug. Tiny examples show exactly where each bites.
| Mistake | Why it breaks | Fix |
|---|---|---|
while(lo <= hi) vs while(lo < hi) |
<= is for exact-match where you return mid inside. Use it with a
converging boundary search and you re-test a size-1 window forever or overshoot. |
< hi for boundary/first-true (half-open). <= hi only when you return
from inside on a hit. |
hi = mid vs hi = mid - 1 |
In first-true search, mid itself may be the answer. hi = mid - 1 would throw
it away and return one-too-far. |
First-true keeps mid: hi = mid. Exact-match discards it: hi = mid - 1. |
lo = mid infinite loop |
When hi = lo + 1, lower-mid gives mid = lo; lo = mid never
advances. Classic hang in max-feasible searches. |
If a branch does lo = mid, use upper mid: mid = lo + (hi - lo + 1) / 2. |
Computing mid = (lo + hi) / 2 |
lo + hi overflows int when both are near 2³¹ (First Bad Version with huge
n). |
Always mid = lo + (hi - lo) / 2. |
Returning lo vs hi vs mid |
After a lo < hi loop, lo == hi so either is fine — but mid
is stale. Guessing here means you didn't decide the return before coding. |
Boundary search → return lo. Last-valid → return stored ans or
lo - 1. Decide at step 8 of the drill.
|
| Losing a candidate answer | In "last true / max feasible," moving on without saving mid loses the best-so-far, and you return the neighbor. | Either use the boundary-converging template (return lo/lo-1), or explicitly
store ans = mid before moving. |
| Wrong feasibility direction | Writing feasible so the strip is T…T F…F but using the min-feasible
(F…F T…T) template returns the opposite end. |
Print feasible(lo), feasible(mid), feasible(hi) once. Confirm the flip direction, then
pick the matching template. |
| Bad initial bounds | hi too small excludes the true answer; lo too big never reaches it. E.g. Koko with
hi = max/2 can miss the answer entirely.
|
lo = smallest legal answer; hi = a value you can prove is always feasible (sum, max element, etc.). |
| lower vs upper bound mix-up | >= gives first occurrence; > gives one-past-last. Swap them and "count
of x" or "last index of x" is off by the frequency of x. |
first ≥ target = lower (>=); first > target = upper (>); last ≤
target = upper − 1. |
| Duplicates break "which side is sorted" | In rotated search with repeats, a[lo]==a[mid]==a[hi] makes the sorted-side test
ambiguous. |
Shrink both ends (lo++, hi--) in that one case; accept O(n) worst case. |
| Integer overflow in feasibility | k*k, sum of weights, or products can exceed int even when the answer fits.
|
Use long inside feasible, or compare with division instead of
multiplication. |
| Accidentally breaking monotonicity | Assuming a condition is monotone when it isn't (e.g. an unsorted input, or a feasibility that isn't actually one-directional) makes every discard invalid. | State the flip explicitly ("bigger K ⇒ always feasible"). If you can't, binary search is the wrong tool. |
Array [5, 7], searching first index with a[i] >= 7. With
hi = mid and lo < hi: mid=0, a[0]=5<7 → lo=1; loop ends, return 1. ✓
Now try the same with lo = mid in a max search and no upper-mid: mid stays 0 forever. That's the
whole infinite-loop bug in two elements.
Read this on the train. If a row's Signal matches your problem, the rest of the row is your plan.
| Pattern | Signal | Search space | Invariant | Movement rule | Return |
|---|---|---|---|---|---|
| 1 · Classic & boundary | Sorted array; want value / position / first-last / insert. | Indices [0,n) or [0,n]. |
Everything left of lo is false; answer in window. |
Exact: mid±1, return on hit. Boundary: true→hi=mid, false→lo=mid+1. |
lo (boundary) or mid/-1 (exact). |
| 2 · Rotated / peak | Not globally sorted; rotated, mountain, or "find a peak." | Indices. | One side is always sorted / slope points to answer. | Peak: uphill→lo=mid+1, else hi=mid. Rotated: identify sorted side,
range-check target. |
lo (peak/min) or index/-1 (target). |
| 3 · On the answer | "Min the max", "max the min", "smallest/largest valid K"; if K works, K±1 works. | Range of possible answers [minCand,maxCand]. |
feasible flips once over the range. | Min: feasible→hi=mid, else lo=mid+1. Max: feasible→lo=mid
(upper-mid!), else hi=mid-1. |
lo = smallest/largest feasible. |
| 4 · Value domain | K-th smallest/largest/median of a huge candidate set; count(≤v) is cheap. | Value range [minV,maxV]. |
count(≤v) non-decreasing. |
count≥k→hi=mid, else lo=mid+1. |
lo = k-th value (a real element). |
| 5 · Helper | Speeding an O(n²) scan; a sorted helper you keep updating. | Inside the helper array. | Helper stays sorted by construction. | Lower/upper bound of x; replace or extend. | Not the search — the outer var (e.g. LIS length). |
| 6 · Partition | Two sorted arrays; median / k-th across both in O(log). | Cut position 0..m in the smaller array. |
Left group size fixed; seek all-left ≤ all-right. | L1>R2→hi=i-1; L2>R1→lo=i+1. |
Median from the 4 border values. |
Before writing a single line:
mid mean?" — finish the sentence.First-true:
lo=0,hi=n; while(lo<hi){mid; check?hi=mid:lo=mid+1} → lo
Exact:
lo=0,hi=n-1; while(lo<=hi){==?return; <?lo=mid+1:hi=mid-1} → -1
Max-feasible: mid=lo+(hi-lo+1)/2; ok?lo=mid:hi=mid-1 → lo
Don't ask "what's the code." Ask "what fact lets me delete half?" — name that fact in words first, and the loop, the boundaries, and the return all follow from it.