Binary Search

A is worth understanding mainly for what it cannot do, because that is what motivates every other sub-variant in this pattern.

1. 1

   The general framing. A binary search locates the boundary of a monotone predicate over an ordered space. Monotone means the predicate flips exactly once as you move right.

2. 2

   Equality is not monotone. On [1,2,2,2,5] with t = 2, the test a[i] == t reads F T T T F. It flips twice, so there is no single boundary to find.

3. 3

   So A returns an arbitrary hit. The search stops at whichever matching index it happens to land on. With duplicates that is unpredictable, and it is why Arrays.binarySearch is unsafe for boundary questions.

4. 4

   Every richer question is a boundary question. First occurrence, last occurrence, count, floor, ceiling — all of them are lowerBound or upperBound with at most one subtraction. So learn those, and get A for free.

The practical consequence: derive existence from the boundary rather than the other way round — int i = lowerBound(a, t); i < n && a[i] == t — and the other four operations come with it at no extra cost.

Never write mid = (lo + hi) / 2. It overflows to a negative index at scale, which surfaces as an ArrayIndexOutOfBounds far from the cause. Always lo + (hi - lo) / 2, or (lo + hi) >>> 1 in Java.

Arrays.binarySearch has two traps: with duplicates it returns an arbitrary matching index rather than a boundary, and on a miss it encodes the insertion point as -(insertionPoint) - 1, which must be decoded with if (i < 0) i = -(i + 1);.

After any boundary search, re-verify before treating the result as a hit. lo is a position, not a promise — check lo < n && a[lo] == target.

a = [1, 2, 2, 2, 5]. Row 1 is exact match; rows 2-5 are lowerBound(2) on the same input. Compare what each one returns.

Exact match returned 2; the boundary search returned 1. Both are correct answers to different questions — but only the second one composes. With upperBound(2) = 4 you also get the count (4 - 1 = 3), the floor and the ceiling, none of which exact match can provide.

• Lead with the predicate framing, not the array. Binary search finds the boundary of a monotone predicate over an ordered space. Saying that first makes rotated arrays, answer-space search and 2D search sound like the same technique — which they are.
• Know why equality is the exception. It is the one test in this pattern that is not monotone, which is exactly why it cannot answer positional questions.
• Prefer your own bounds to the library call. Arrays.binarySearch is fine for distinct values and a yes/no. For anything else it is a liability, and saying so unprompted reads as experience.
• The overflow-safe mid is not optional. It costs nothing and prevents a bug that only appears at scale, which is the worst kind.

• ✗mid = (lo + hi) / 2

  Symptom: integer overflow at scale -> negative index -> ArrayIndexOutOfBounds, far from the cause.

  Prevention: Always lo + (hi - lo) / 2. In Java (lo + hi) >>> 1 also works.

• ✗Using Arrays.binarySearch when duplicates exist

  Symptom: an arbitrary matching index, so first/last/count answers are silently wrong.

  Prevention: Write your own lowerBound / upperBound.

• ✗Forgetting the -(insertionPoint) - 1 decoding

  Symptom: a negative number used as a real index.

  Prevention: if (i < 0) i = -(i + 1); immediately after the call.

• ✗Treating a boundary result as a hit without checking

  Symptom: a bogus index returned instead of not found.

  Prevention: Re-verify: lo < n && a[lo] == target.

Three design choices carry this template, and each one is a line you should be able to justify on request.

1. 1

   The invariant. Everything in [0, lo) is < target; everything in [hi, n) is >= target. The answer is the boundary between them, which is why lo == hi at exit is the answer.

2. 2

   Why hi starts at n, exclusive. n is a legal return value — it means no element qualifies. Starting at n - 1 makes that answer unrepresentable and collapses not found into last index.

3. 3

   Why the branches are asymmetric. a[mid] < target proves mid cannot be the answer, so lo = mid + 1 skips it. Otherwise mid might be the answer, so hi = mid keeps it inside the range.

4. 4

   Termination. mid is always in [lo, hi-1], so hi = mid strictly decreases hi and lo = mid + 1 strictly increases lo. The interval shrinks every iteration — no infinite loop is possible.

One operator apart, and the invariant that makes both correct: lowerBound tests a[mid] < target; upperBound tests a[mid] <= target. Everything below lo is under the boundary and everything from hi up is at or above it — so lo == hi at exit is the boundary itself.

Verified on [1,2,2,2,5]: lowerBound(2) = 1, upperBound(2) = 4, lowerBound(0) = 0, lowerBound(9) = 5. Worth checking any implementation against all four, especially the two out-of-range cases.

Memorise the four derived lines, not four algorithms. Existence, count, floor and ceiling all fall out of the two bounds, and the gate asks you to derive all four.

A boundary is a position, not a hit. After the search, a[lo] may not equal the target at all — always re-verify before reporting found.

a = [1, 2, 2, 2, 5], target 3. The target is absent, and the search still returns something useful — which is the entire point of a boundary.

Returns 4 — the position where a 3 would go, and the index of the least element >= 3. Note a[4] = 5, not 3, so an existence check correctly reports absent. Had hi started at n - 1 = 4, a target larger than every element could never return 5 and not found would be indistinguishable from last index.

• This is the foundation gate, and it is timed. Both functions blind, under three minutes, zero compile errors, plus all four derived operations. The gate says explicitly: do not proceed past it.
• State the invariant, not the code. Below lo everything is less; from hi up everything is at least. That sentence reconstructs the template from scratch if you blank.
• The exclusive hi is a correctness decision. It exists so that no element qualifies is representable. Candidates who use n - 1 here usually have not thought about the absent case.
• Half-open versus inclusive is a per-file policy. Mixing the two between problems is called out as the single largest source of binary-search bugs. Pick one shape and commit.

• ✗Starting hi at n - 1

  Symptom: lowerBound can never return n, so not found collapses into last index.

  Prevention: Boundary searches use hi = n, exclusive. n is a legal answer.

• ✗Writing while (lo <= hi) with hi = mid

  Symptom: infinite loop.

  Prevention: < pairs with hi = mid; <= pairs with mid ± 1 on both branches. Never cross them.

• ✗hi = mid - 1 in a lower-bound search

  Symptom: the answer is skipped whenever mid is itself the boundary.

  Prevention: mid might be the answer, so it stays in range: hi = mid.

• ✗Reporting lo as a hit without checking

  Symptom: a valid index returned for a value that is not present.

  Prevention: i < n && a[i] == t — the boundary tells you where, not whether.

The gate for this sub-variant asks specifically why these cannot infinite-loop. Here is the argument, plus the trap in the alternative form.

1. 1

   The requirement. ok() must be monotone over [lo, hi] — F...F T...T for firstTrue, T...T F...F for lastTrue. Exactly one flip.

2. 2

   firstTrue. On a hit, record mid in res and search left for an earlier one (hi = mid - 1). On a miss, go right (lo = mid + 1).

3. 3

   lastTrue. The mirror: on a hit, record and search right (lo = mid + 1); on a miss, go left (hi = mid - 1).

4. 4

   Why neither can hang. Every branch of both templates moves a bound by at least one. The interval [lo, hi] is therefore strictly smaller on every iteration and must reach empty.

Why the res-tracking form, and the one policy that saves you: both branches strictly move a bound (mid ± 1), so the interval shrinks every iteration unconditionally. The alternative while (lo < hi) plus lo = mid form requires the ceiling mid mid = lo + (hi - lo + 1) / 2 or it hangs forever when hi == lo + 1. Simplest policy: never write lo = mid.

Verified on [1,3,5,7]: lastTrue(a[i] <= 5) = 2, firstTrue(a[i] >= 5) = 2, firstTrue(a[i] >= 99) = 4, which is hi + 1 — the never-true sentinel.

Handle the sentinel at the call site. hi + 1 and lo - 1 are out-of-range by construction, so the caller must check before indexing with the result.

a = [1, 3, 5, 7], lo = 0, hi = 3, res initialised to hi + 1 = 4. Watch res get written once and then improved on.

Returns 2. Run the same template with ok(i) = a[i] >= 99 and no branch ever fires the true case, so res keeps its initial hi + 1 = 4 — an out-of-range sentinel meaning never true. The caller must check for it rather than indexing blindly.

• This template retires most of the pattern. Sub-variants D through M are almost entirely choose lo, hi and ok(). If you own C, the rest is problem modelling rather than new algorithms.
• Be able to state the no-hang argument. The gate asks for it directly. Both branches move a bound by one, so the interval strictly shrinks is the whole answer.
• Know the mid-formula rule even though you avoid it. Floor mid pairs with hi = mid; ceiling mid pairs with lo = mid. The gate asks for the rule precisely because the alternative form is common in other people's code.
• Monotonicity is a proof obligation, not a vibe. Write out ok(x) implies ok(x+1) before coding. If you cannot, it is not a binary search — and the failure mode is a confident, wrong answer rather than a crash.

• ✗lo = mid with floor mid

  Symptom: infinite loop whenever hi == lo + 1.

  Prevention: If you write lo = mid, you must write mid = lo + (hi - lo + 1) / 2. Or use the res form and never write lo = mid at all.

• ✗hi = mid with ceiling mid

  Symptom: infinite loop — the mirror of the above.

  Prevention: Floor mid pairs with hi = mid; ceiling mid pairs with lo = mid. Never cross them.

• ✗Mixing [lo, hi] and [lo, hi) between problems

  Symptom: sporadic off-by-one that passes some tests and fails others.

  Prevention: Pick one convention per template and label it in a comment.

• ✗Running it on a non-monotone predicate

  Symptom: converges to an arbitrary point inside the valid region — no crash, just a wrong answer.

  Prevention: Prove the implication before coding. If it will not prove, it is not binary search.

Both halves of this sub-variant hinge on one comparison choice, and the argument against the obvious alternative is concrete.

1. 1

   The structure. A rotation splits the array into two sorted runs, and the minimum sits at the boundary between them — the pivot.

2. 2

   The LC 153 predicate. a[mid] > a[hi] means mid is inside the left run, so the pivot is strictly to the right: lo = mid + 1. Otherwise mid could itself be the minimum, so hi = mid keeps it.

3. 3

   Why not a[lo]. On a non-rotated array such as [1,2,3], a[mid] > a[lo] is true — and would send the search right, away from the minimum at index 0. The unrotated array is a legal input, so the comparison is simply wrong.

4. 4

   LC 33's sorted-half test. a[lo] <= a[mid] identifies the sorted half. The <= matters: when lo == mid the left half is the single element a[lo], which is still trivially sorted, and a strict < misclassifies it.

The comparison that must be against a[hi]: on a non-rotated array [1,2,3], a[mid] > a[lo] is true and would send you right — wrong. Comparing to a[hi] is correct in both the rotated and the unrotated case.

LC 154 — duplicates destroy the guarantee. When a[mid] == a[hi] the comparison carries zero information: the pivot could be on either side. The only safe move is hi--, shrinking by one, which gives O(n) worst case on input like [1,1,1,...,1,0,1,...]. State that worst case rather than claiming O(log n).

Verified: [4,5,6,7,0,1,2] gives find(0) = 4 and find(3) = -1; the single-element array [1] gives find(1) = 0.

The two problems are genuinely different. LC 153 is a boundary search on a derived predicate; LC 33 is a containment test inside a known-sorted half. Learning one does not give you the other.

At every step, identify the sorted half first, then ask whether the target is inside it. That ordering is the algorithm.

Found at index 4. Notice step 2: the left half [0, 1] was the sorted one even though we were in the second run — the test is about the window [lo, hi], not about the original array. Getting that right is why the containment check uses a[lo] and a[hi] rather than any global reasoning.

• The a[hi] argument is the gate. Write LC 153 blind and explain why comparing to a[lo] breaks. The counterexample is the unrotated array, and it is worth having [1,2,3] ready to say.
• Say the <= out loud in LC 33. a[lo] <= a[mid], because at lo == mid the left half is one element and still counts as sorted. A strict < fails on two-element windows.
• Duplicates change the complexity, not just the code. Volunteering LC 154 is O(n) worst case, because a[mid] == a[hi] carries no information is a strong signal. Claiming O(log n) there is a weak one.
• This is sub-variant C with a derived predicate. Nothing about the loop is new — only ok() changed. Framing it that way is the payoff of learning C properly.

• ✗Comparing a[mid] to a[lo] in the pivot search

  Symptom: fails on a non-rotated array, which is a legal input.

  Prevention: Always compare a[mid] to a[hi].

• ✗Writing a[lo] < a[mid] (strict) in LC 33

  Symptom: fails whenever lo == mid, i.e. on two-element windows.

  Prevention: Use a[lo] <= a[mid] — a single element is trivially a sorted half.

• ✗Claiming O(log n) for LC 154

  Symptom: an incorrect complexity claim on duplicate-heavy input.

  Prevention: a[mid] == a[hi] gives no information, so you shrink by one: O(n) worst case. Say it.

• ✗Testing containment before identifying the sorted half

  Symptom: the containment test is meaningless on an unsorted range.

  Prevention: Identify the clean half first, then test the target against its two ends.

The argument is short and it is exactly what the gate asks for, so it is worth being able to give verbatim.

1. 1

   The invariant. [lo, hi] always contains a peak, given a[-1] = a[n] = -infinity. That is what is being maintained — not any ordering of the values.

2. 2

   The ascending branch. If a[mid] < a[mid+1] the values rise going right. Since the far right eventually falls away to the -infinity sentinel, something must turn over: a peak exists strictly right of mid, so lo = mid + 1 preserves the invariant.

3. 3

   The descending branch. If a[mid] >= a[mid+1] the values fall going right, so the rise that led to mid has already turned over — mid itself could be the peak. hi = mid keeps it in range.

4. 4

   The bound must be strict. lo < hi, not <=. With <= you would read a[mid + 1] out of bounds when mid == n - 1; with <, floor mid guarantees mid + 1 <= hi always.

The sentence the gate is asking for: binary search needs a monotone predicate, not sorted data. The invariant a peak exists in [lo, hi] is preserved by both branches, and that is the whole proof.

LC 852 is the same machine on a guaranteed mountain. Nothing changes except that the input promises exactly one peak, so any peak you find is the peak.

LC 1095 composes it. Find the peak, then run two ordinary boundary searches — one ascending and one descending. A good demonstration that these sub-variants stack.

Flat tops need care. The template treats a[mid] >= a[mid+1] as keep mid, which is correct when the problem guarantees distinct neighbours. If plateaus are allowed, re-read the problem's definition of a peak before reusing this.

a = [1, 2, 1, 3, 5, 6, 4]. Nothing is sorted, and the search still converges in three steps.

Returns index 5. Note that index 1 is also a peak (a[1] = 2 beats both neighbours) and the search never looked at it — which is fine, because the problem asks for a peak. If it asked for the largest, this approach would be invalid.

• Lead with the invariant, not the code. A peak exists in [lo, hi] is what the gate wants, and it is what makes an unsorted binary search sound rather than lucky.
• This is the proof that the pattern is about predicates. If someone believes binary search requires a sorted array, this problem is the counterexample to hand them.
• The strict bound is a real bug prevention. lo < hi exists so that a[mid + 1] is always in range. It is not a style choice.
• Any peak, not the best peak. Saying that distinction unprompted shows you understand what the invariant does and does not promise.

• ✗Using while (lo <= hi)

  Symptom: reads a[mid + 1] out of bounds at the last index.

  Prevention: Peak search uses lo < hi, which makes mid + 1 <= hi always true with floor mid.

• ✗Assuming the input must be sorted

  Symptom: you reject a valid approach and fall back to an O(n) scan.

  Prevention: The requirement is a monotone predicate. The slope qualifies; the data does not have to.

• ✗Expecting the global maximum

  Symptom: wrong answers on arrays with several peaks.

  Prevention: The invariant only guarantees a peak inside the window.

• ✗Comparing against a[mid - 1] instead

  Symptom: an out-of-bounds read at index 0, and a mirrored set of boundary problems.

  Prevention: Compare forwards, a[mid] against a[mid + 1], and let the strict bound protect it.

Two different structural expectations, two different drift functions — and the same search underneath both.

1. 1

   LC 1539 — define the drift. missing(i) = a[i] - (i + 1) counts how many positive integers are absent at or before index i. In a gapless array it would be zero everywhere.

2. 2

   Show it is monotone. a is strictly increasing, so each step right adds at least one to the value while adding exactly one to the index. missing() therefore never decreases — which makes it searchable.

3. 3

   Read off the answer. Find the first index with missing(i) >= k. That index has res array elements before it, so the k-th missing number is res + k. Initialise res = a.length, meaning every element precedes the answer.

4. 4

   LC 540 — a parity drift. Before the single element, pairs sit at (even, odd) indices; after it, at (odd, even). So snap mid down to an even index and test a[mid] == a[mid + 1]: intact pairing means the single element is to the right, broken means it is at or left of mid.

The move that defines this sub-variant: construct a drift function — the gap between where a value is and where it ought to be — and binary search that. The search is ordinary; building the monotone function is the skill.

The res + k return surprises people. res counts the array elements that come before the answer, and k counts the missing numbers up to it. Their sum is the value itself. The gate asks you to explain that, not just to write it.

LC 540's mid % 2 == 1 snap is doing the parity alignment. Without it, mid may point at the second half of a pair and the pairing test compares across a boundary rather than within a pair.

Both problems degrade gracefully to O(n) scans, which is what makes the O(log n) requirement the signal that a drift function is wanted.

a = [2, 3, 4, 7, 11], k = 5. The drift row is the whole trick; once it is written down the search is a plain first-true.

res = 4, so the answer is res + k = 4 + 5 = 9. Check it by hand: the array holds 2, 3, 4, 7, 11, so the missing positives are 1, 5, 6, 8, 9, ... and the fifth is indeed 9. Four array elements precede it, which is exactly what res counted.

• Derive the drift function out loud, do not recall it. The gate is explicit: derive a[i] - (i+1) yourself and explain the res + k return. Recalling the formula without the derivation is what it is designed to catch.
• Monotonicity comes from strict increase. Each step adds at least one to the value and exactly one to the index, so the gap can never shrink. That one sentence licenses the whole search.
• Parity is just another structural expectation. LC 540 measures drift in pairing alignment rather than in value. Same category, different quantity — which is the transfer worth noticing.
• This category is under-taught and over-asked. Recognising index-vs-value drift as a named thing is most of the benefit of the taxonomy here.

• ✗Searching the values instead of the drift

  Symptom: no monotone predicate exists over the raw values, so the search converges to nonsense.

  Prevention: Build the drift function first, confirm it is non-decreasing, then search it.

• ✗Returning res instead of res + k

  Symptom: an index returned where a value was asked for.

  Prevention: res elements precede the answer; the answer is the k-th missing number after them.

• ✗Forgetting the even-snap in LC 540

  Symptom: the pairing test straddles two different pairs and the result is arbitrary.

  Prevention: if (mid % 2 == 1) mid--; before testing a[mid] == a[mid + 1].

• ✗Initialising res to -1 or 0

  Symptom: wrong answer when every element precedes the target.

  Prevention: res = a.length — the case where the k-th missing number is beyond the whole array.

Answer-space search is easy to write and easy to get subtly wrong. Each checklist item corresponds to a specific, named failure.

1. 1

   Establish the direction. Bigger x makes the constraint easier to satisfy, so feasible reads F...F T...T and you want the first true.

2. 2

   lo must be the smallest legal candidate. Not simply 1. In LC 1011 a single package must fit in one trip, so any capacity below max(weights) is infeasible forever — and starting there lets the search return an impossible answer.

3. 3

   hi must be provably feasible. Choose something you can argue always works: the sum of all weights (one giant trip), the maximum pile (one pile per hour), the full range. Otherwise the search can converge past the end of the feasible region and return an infeasible value silently.

4. 4

   Prove the implication. feasible(x) must imply feasible(x+1). If it does not, the predicate is not monotone and the search converges to an arbitrary point in the valid region — with no crash to warn you.

The bound bug this sub-variant exists to teach: lo is the smallest legal candidate, not 1. In LC 1011 a single item must fit in one trip, so lo = max(weights); and hi must be a value you can prove always works, such as sum(weights) — one giant trip.

LC 875 Koko bounds: lo = 1 because speed 0 eats nothing, and hi = max(piles) because one pile per hour always finishes in time. Verified: ([3,6,7,11], 8) gives 4; ([30,11,23,4,20], 5) gives 30.

Ceiling division has its own trap. Write (v + speed - 1) / speed in long, not v / speed + 1 — the naive form is off by one whenever the division is exact.

Overflow lives inside feasible, not in the search. Every accumulation in the predicate needs long: mid * mid, m * k, sums of weights. The failure is a wrong feasibility verdict, so it produces a wrong answer with no crash.

lo = 1, hi = max(piles) = 11. hours(speed) sums the ceiling divisions; the search is a plain first-true over the answer space.

Answer 4. Notice that speeds 4 and 5 both finish in exactly 8 hours — the search does not stop at the first feasible value it meets, it keeps narrowing to the smallest one. That is what distinguishes a first-true search from a linear scan that returns early.

• Name lo, hi and feasible before writing any code. That is the gate, word for word — plus a justification for why hi is always feasible. Doing it out loud also catches the lo bug before it exists.
• The lo bug is the signature error of this sub-variant. Capacity problems need lo = max(item). Starting at 1 returns an answer that cannot pack a single item, and small tests often miss it.
• Monotonicity is a proof obligation. Write out feasible(x) implies feasible(x+1) before coding. Non-monotone predicates fail silently, which is the worst failure mode in this whole pattern.
• LC 410 is LC 1011 with different nouns. The gate says so directly: if 410 does not feel like 1011, you learned the problem rather than the pattern. Write the mapping between them explicitly.
• Say the complexity as O(n log(range)). It makes clear you know the log comes from the answer space, not from the data.

• ✗lo too low — e.g. 1 in LC 1011

  Symptom: returns an impossible answer; a single item never fits.

  Prevention: lo is the smallest legal candidate. For capacity problems that is max(weights).

• ✗hi not provably feasible

  Symptom: the search converges past the feasible region and returns an infeasible value, silently.

  Prevention: Pick hi you can argue always works: sum of all, max element, full range.

• ✗Non-monotone feasible

  Symptom: converges to an arbitrary point inside the valid region — no crash, wrong answer.

  Prevention: Prove feasible(x) implies feasible(x+1) on paper first.

• ✗Ceiling division as v / speed + 1

  Symptom: off by one whenever the division is exact.

  Prevention: (v + speed - 1) / speed, accumulated in long.

The correctness argument is G's, mirrored. The interesting part is the mechanical failure that the mirroring introduces.

1. 1

   Establish the direction. Bigger x is harder, so feasible reads T...T F...F and the answer is the last true.

2. 2

   The natural loop shape needs lo = mid. To keep a feasible mid as a candidate while searching right, you write lo = mid rather than lo = mid + 1 — because mid itself might be the answer.

3. 3

   That is exactly what hangs. When hi == lo + 1, floor mid gives mid == lo. So lo = mid leaves lo unchanged, hi unchanged, and the loop spins forever on a two-element range.

4. 4

   The fix, and the general rule. Use the ceiling: mid = lo + (hi - lo + 1) / 2, which lands on hi instead of lo. The rule underneath: floor mid pairs with hi = mid; ceiling mid pairs with lo = mid.

The one place the mid formula changes — and how to never need it: with lo < hi and lo = mid you must write mid = lo + (hi - lo + 1) / 2, the ceiling, or the loop hangs when hi == lo + 1. If you would rather never think about this again, use lastTrue(lo, hi, ok) from §C. Recommended.

LC 1552's greedy check is the other half of the problem. canPlace(gap) places balls leftmost-first and counts them; greedy leftmost placement is optimal, because delaying a placement can never allow more balls later.

The gate accepts either answer. Explain why the ceiling mid is needed, or explain why lastTrue sidesteps the issue entirely. Both demonstrate you understand the trap.

Everything from G still applies — lo and hi justification, monotonicity proof, long inside the predicate. Only the direction and the mid formula differ.

lo = 1, hi = 7 - 1 = 6. Every mid below is a ceiling mid — watch step 3, where the floor version would have hung.

Answer 3. Step 3 is the trap made concrete: with lo = 2, hi = 3, the floor mid would be 2 + (3-2)/2 = 2, so lo = mid would set lo = 2 — unchanged — and the loop would spin forever. The ceiling gives 3 instead, and the search terminates.

• The hang is the lesson, so be able to construct it. lo = 2, hi = 3, floor mid is 2, lo = mid is a no-op. Having that two-element example ready is worth more than remembering the formula.
• State the pairing rule, not just the fix. Floor mid with hi = mid; ceiling mid with lo = mid. One rule covers both directions and both failure modes.
• lastTrue is a legitimate answer to the gate. Preferring the res-tracking template because it has no mid-formula trap is a judgement call, and saying so explicitly reads better than silently avoiding the topic.
• Justify the greedy inside feasible. For LC 1552, leftmost placement is optimal. Interviewers often probe the checker rather than the search, because that is where the real reasoning is.

• ✗Floor mid with lo = mid

  Symptom: infinite loop whenever hi == lo + 1.

  Prevention: Ceiling mid: mid = lo + (hi - lo + 1) / 2. Or use lastTrue and never write lo = mid.

• ✗Ceiling mid with hi = mid

  Symptom: infinite loop, the mirror image.

  Prevention: Never cross the pairing: floor with hi = mid, ceiling with lo = mid.

• ✗Using G's first-true search on a maximise problem

  Symptom: returns the smallest feasible value — typically the trivial answer.

  Prevention: Establish the direction first. Bigger harder means last-true.

• ✗An unjustified greedy inside feasible

  Symptom: a plausible checker that is subtly not optimal, so the whole search is wrong.

  Prevention: Argue the greedy. For 1552, leftmost placement can never do worse than delaying.

The search is straightforward. The part that gets asked as a follow-up is why the returned value is guaranteed to actually exist in the collection.

1. 1

   The space. Values, bounded below by the smallest element and above by the largest. For a sorted matrix that is m[0][0] and m[n-1][n-1].

2. 2

   The predicate. countLE(v) >= k. It is non-decreasing in v, because raising v can only add elements to the count — never remove them. Monotone, therefore searchable.

3. 3

   The search. First-true gives the smallest v for which at least k elements are <= v. That is the definition of the k-th smallest.

4. 4

   Why lo is a real element. This is the follow-up. If lo were absent from the collection, then nothing lies between lo - 1 and lo, so countLE(lo - 1) == countLE(lo) >= k — meaning lo - 1 also satisfies the predicate, contradicting the minimality of lo.

Why the returned lo is guaranteed to be a real matrix element — have this ready: lo is the smallest value v with countLE(v) >= k. If v were not in the matrix, then countLE(v-1) == countLE(v) >= k, so v-1 would also satisfy the predicate — contradicting minimality.

The staircase counter is sub-variant J's technique, reused as a predicate. That composition — one sub-variant supplying the ok() for another — is the clearest sign the taxonomy is carving at real joints.

Cost is O(n log(range)), not O(n^2 log n). The counting call is linear and the search adds a log over the value range.

The third 2D case belongs here. A matrix sorted only within rows cannot be flattened or walked as a staircase — you binary search the value range with a per-row upperBound count.

m = [[1,5,9],[10,11,13],[12,13,15]], k = 8. lo = 1, hi = 15. Note that mid need not be a matrix element at all — only the final answer must be.

Answer 13. Step 3 is the reason the follow-up argument matters: mid = 14 satisfied the predicate, but 14 is not in the matrix. The search kept narrowing, and the value it finally settled on — the smallest satisfying value — is guaranteed to be real, by the contradiction argument above.

• Have the realness argument ready before you are asked. The gate is explicit: explain why the returned value is a real matrix element. A correct program you cannot defend is what it is designed to catch.
• Name the difference from G and H. There the predicate simulates feasibility; here it counts. Same template, genuinely different modelling — which is why it is its own row.
• Intermediate mid values need not exist. That surprises people and is worth saying explicitly, because it is exactly what makes the final-answer argument necessary.
• The counting function is where the cleverness lives. The binary search is boilerplate. Writing an O(n) counter for an O(n^2) collection is the actual work.

• ✗Assuming mid must be a matrix element

  Symptom: you constrain the search unnecessarily, or doubt a correct answer.

  Prevention: The search runs over the value range. Only the final answer is guaranteed real, and there is a proof for that.

• ✗Counting with an O(n^2) scan

  Symptom: correct answers, and the complexity advantage is thrown away.

  Prevention: Use the staircase: O(n) per call, cnt += r + 1 when the cell qualifies.

• ✗Using countLE(v) > k instead of >= k

  Symptom: off by one — you find the value after the k-th.

  Prevention: >= k — you want the smallest v with at least k elements below or equal.

• ✗Applying it to a small collection

  Symptom: a complicated solution where sorting would do.

  Prevention: This is for collections you cannot materialise. If you can build it, build it.

Each technique needs a specific promise. Naming the promise is the work; the code is short either way.

1. 1

   Case 1 — the flattening guarantee. If every row starts after the previous row ends, then reading the matrix row by row produces a sorted 1D array. An ordinary boundary search over [0, m*n) applies directly.

2. 2

   Indexing the flattening. mat[mid / n][mid % n] where n is the column count. Using the row count here produces garbage indices that often stay in bounds, so it fails silently.

3. 3

   Case 2 — why flattening is illegal. When only rows and columns are sorted, row starts are not globally ordered: in the example above 2 follows 7 in flat order. There is no monotone predicate over the flat index, so there is nothing to binary search.

4. 4

   The staircase instead. Start at the top-right. If the cell is too big, the entire column below it is too big — drop the column. If it is too small, the entire row to its left is too small — drop the row. Each comparison removes a full row or column, giving O(m + n).

The distinction that decides everything — and the gate: read the constraint sentence: is row[i][0] > row[i-1][last] guaranteed? If yes, flatten. If only rows and columns are sorted, flattening is illegal and you want the staircase. Stating which is which from the constraints alone is the gate.

The staircase is strictly O(m + n), not O(log). That is optimal for this guarantee, and saying so pre-empts the can you do better? follow-up — you cannot, in general.

Corner choice matters. Top-right (or bottom-left) works because both directions are informative there. Starting at the top-left gives you two directions that both increase, so no comparison eliminates anything.

The counting form starts bottom-left — see sub-variant I, where the same walk is reused as countLE rather than as a search.

After a flattened boundary search, re-verify: lo < m*n && mat[lo/n][lo%n] == t.

[[1,4,7],[2,5,8],[3,6,9]]. Flatten it and you get 1,4,7,2,5,8,3,6,9 — not sorted, so LC 74's approach is illegal here. The staircase starts top-right.

Three comparisons for a nine-cell matrix. Each step discarded an entire row or column rather than a single cell, which is where the O(m + n) comes from. Had you flattened instead, the binary search would have compared against a sequence that is not sorted and returned a confident, wrong answer.

• The gate is a reading exercise, not a coding one. Look at LC 74 and LC 240 and state, from the constraints alone, which one may be flattened. The failure mode is writing code before reading the guarantee.
• Say why the corner is top-right. Both directions carry information there. From the top-left, everything to the right and everything below is larger, so no comparison eliminates anything.
• n is the column count, always. The /n and %n decomposition is the one line where row and column counts get swapped, and the result usually stays in bounds — so it fails quietly.
• Three guarantees, three techniques, one family. Naming all three unprompted shows you have a taxonomy rather than a memorised pair of problems.

• ✗Flattening LC 240 as if it were LC 74

  Symptom: wrong answers on staircase-sorted matrices; the code looks perfectly reasonable.

  Prevention: Read the constraint: is row[i][0] > row[i-1][last] guaranteed? If not, flattening is invalid.

• ✗mid / n using the row count

  Symptom: garbage indices that often remain in bounds, so it fails silently.

  Prevention: n is the number of columns.

• ✗Starting the staircase at the top-left

  Symptom: no comparison eliminates anything and the walk degenerates.

  Prevention: Start top-right for search, bottom-left for counting. Both directions must be informative.

• ✗Returning the flattened boundary without verifying

  Symptom: a position reported as a hit for an absent value.

  Prevention: lo < m*n && mat[lo/n][lo%n] == t.

Almost every line of this template exists to eliminate a special case. Knowing which case each one kills is what makes it writable from memory.

1. 1

   The search space. i in [0, m] — how many elements to take from A. Then j = half - i is determined, so one variable searches a two-dimensional-looking problem.

2. 2

   Why swap so A is shorter. If A were the longer array, j = half - i could fall outside [0, n] for legal values of i, and the sentinels would not save you. The initial swap makes that impossible.

3. 3

   The validity test. aL <= bR && bL <= aR. Because each array is internally sorted, these two cross-comparisons are exactly the condition that everything left is at most everything right.

4. 4

   Which way to move. aL > bR means the left side holds something too large — you took too many from A, so hi = i - 1. Otherwise you took too few, so lo = i + 1.

The convention that makes the odd case free: half = (m + n + 1) / 2 puts the extra element on the left when the total is odd, so the median is simply max(aL, bL) with no separate branch. The ±infinity sentinels remove every empty-side edge case.

Verified: ([1,3], [2]) gives 2.0; ([1,2], [3,4]) gives 2.5; ([], [1]) gives 1.0. The last one is the case the sentinels exist for.

The even-case average overflows in int. Integer.MIN_VALUE + Integer.MAX_VALUE is reachable when both sentinels appear, so cast: (Math.max(aL, bL) + (long) Math.min(aR, bR)) / 2.0.

The gate asks specifically for the swap. Being able to explain why A must be the shorter array is the difference between having typed this template and understanding it.

After the swap, A = [2] (m = 1) and B = [1, 3] (n = 2), so half = (1 + 2 + 1) / 2 = 2. The search runs over i in [0, 1].

Two iterations. Notice how much the sentinels absorbed: at i = 0 the left side of A is empty, and at i = 1 its right side is — both handled by ±infinity rather than by branching. Strip the sentinels out and this template roughly doubles in length.

• Budget multiple attempts, deliberately. The gate calls this the hardest single template in the document and recommends three separate attempts across a week. Treating it as a one-sitting problem is how it never sticks.
• Explain the swap unprompted. It is not an optimisation — it is what keeps j inside [0, n]. That is the detail the gate names.
• The sentinels are the design, not a detail. Every empty-side case disappears into ±infinity. Pointing that out shows you see why the template is short.
• half with the +1 handles parity for free. Odd totals put the extra element on the left, so the odd case is a single max. Without the +1 you need two branches.
• Know when not to reach for it. If O(m + n) passes, merge. This template is for when the constraints explicitly forbid that.

• ✗Not swapping so A is the shorter array

  Symptom: j falls outside [0, n] and the sentinels cannot rescue it.

  Prevention: if (A.length > B.length) return solve(B, A); as the first line.

• ✗Omitting the ±infinity sentinels

  Symptom: index-out-of-bounds on every empty-side case, or a thicket of special-case branches.

  Prevention: aL = -inf when i == 0, aR = +inf when i == m, and the same for B.

• ✗Using half = (m + n) / 2

  Symptom: the odd case needs a separate branch and usually gets it wrong.

  Prevention: (m + n + 1) / 2 puts the extra element on the left so the odd median is just max(aL, bL).

• ✗Averaging in int

  Symptom: overflow when both sentinels participate.

  Prevention: Cast one operand: (max(aL, bL) + (long) min(aR, bR)) / 2.0.

Three of this pattern's habits are wrong on reals, and understanding why is more useful than memorising the replacement.

1. 1

   There is no smallest step. mid + 1 is meaningless on the reals, so the integer trick of excluding mid by stepping past it has no analogue. lo = mid is the only option.

2. 2

   An epsilon loop can hang. Once hi - lo falls below what a double can represent, the subtraction stops producing a smaller value. while (hi - lo > eps) then never terminates.

3. 3

   A fixed count cannot stall. With for (int i = 0; i < 100; i++) there is no condition to fail. The loop runs, converges as far as the representation allows, and stops.

4. 4

   So lo = mid becomes safe. The thing that made it dangerous in an integer search — being the loop's termination condition — is simply absent.

The rule that inverts on the reals: lo = mid would be an infinite-loop bug in an integer search, but here it is correct and safe: there is no termination condition to stall, because the loop runs a fixed 100 times regardless.

LC 69 Sqrt(x) has an integer answer but teaches the overflow lesson. mid * mid overflows int, so either cast — (long) mid * mid <= x — or restructure as mid <= x / mid. It also uses the last-true form, so it needs the ceiling mid from sub-variant H.

Never write an epsilon loop, even when it seems to work. It is the difference between code that passes and code that hangs on one adversarial input.

lo = 0, hi = 2, feasible(x) = x*x <= 2. Five of the hundred iterations are shown; the interval is already narrowing on 1.41421...

After five halvings the interval has width 0.0625 and brackets 1.41421. After a hundred it is narrower than a double can distinguish — so returning either endpoint is equally correct. Nowhere in the loop is there a condition that could fail to be met.

• The inverted rule is the memorable part. lo = mid is a bug in integers and correct on reals. Knowing why — there is no termination condition — is the actual understanding.
• Justify 100 with arithmetic, not superstition. A 10^9 range halved 100 times is about 10^-21, far past double precision. That is a sentence, not a guess.
• Name the epsilon-loop failure precisely. It hangs when hi - lo stops shrinking at the limits of representation — not merely it might be slow.
• Know the boundary of the technique. Binary search finds boundaries. A continuous maximum needs ternary search or a search on the sign of the derivative — reaching for plain binary search there is simply wrong.

• ✗Using an epsilon loop

  Symptom: hangs when hi - lo stops shrinking at double precision.

  Prevention: Fixed iteration count, 100 halvings. No termination condition, no stall.

• ✗Writing lo = mid + 1 on reals

  Symptom: skips the answer by a whole unit, which is meaningless in a continuous space.

  Prevention: lo = mid. The integer rule does not apply here.

• ✗mid * mid in int for LC 69

  Symptom: silent overflow and a wrong result on large inputs.

  Prevention: (long) mid * mid <= x, or restructure as mid <= x / mid.

• ✗Binary searching for a continuous extremum

  Symptom: converges to an arbitrary point rather than the maximum.

  Prevention: Ternary search, or binary search on the sign of the derivative.

LIS by patience sorting is four lines and almost everyone can reproduce them. The gate is about whether you know what the array actually contains.

1. 1

   The definition. tails[k] is the smallest possible tail of any increasing subsequence of length k + 1. Not a particular subsequence — the best possible ending value for that length.

2. 2

   Why it is sorted. A longer increasing subsequence must end at least as high as a shorter one can, so tails is non-decreasing by construction — which is what makes it binary searchable.

3. 3

   Why you overwrite the first tail >= v. That is lowerBound(v). Replacing it keeps every entry as small as possible, maximising the chance that some future element can extend that length. If the position is past the end, the LIS has grown.

4. 4

   Why the array is not the subsequence. Entries are written at different times from different positions, and nothing forces them to be mutually compatible. tails can hold values that could never coexist in one increasing run through the original array.

The thing the gate asks you to explain: tails is not the actual subsequence — its entries can come from positions that could never coexist in one increasing run. Only its length is meaningful.

Strict versus non-strict changes the boundary function. For a non-strictly increasing subsequence you want upperBound semantics rather than lowerBound.

Prefer your own bounds to Arrays.binarySearch whenever duplicates exist. The library call finds an equal element, which is not necessarily the boundary you need, and it encodes misses as -(insertionPoint) - 1 — decode with if (i < 0) i = -(i + 1);.

Galloping handles unbounded spaces. Double a bound until it overshoots, then binary search the bracket [bound/2, bound]. Total cost O(log answer), with no need to know the size in advance.

Watch the final tails. It has the right length, and it is not a subsequence of the input at all.

The answer is 3, which is correct — the LIS is [4, 5, 6]. But the final tails is [1, 2, 6], and that is not a subsequence of the input: 6 occurs at index 2, before the 1 at index 3 and the 2 at index 4. The length survived; the contents did not. That is exactly what the gate wants you to be able to say.

• This is the form that actually appears in interviews. Rarely as solve this binary search; usually as a harder problem whose intended solution has a lowerBound in the middle of it. Recognising the opening is the skill.
• Be precise about what tails holds. The smallest possible tail for each length — not a subsequence, not the answer. The counterexample above is worth keeping in your head.
• Prefer hand-written bounds over the library call. Arrays.binarySearch is a liability with duplicates and needs miss-decoding. Your own lowerBound has neither problem.
• Galloping is the answer to unbounded. Doubling to find a bracket, then searching it, is the standard move for unknown-length or infinite spaces — and it stays O(log answer).

• ✗Returning tails as the subsequence

  Symptom: a plausible-looking array that is not a subsequence of the input.

  Prevention: Only the length is meaningful. Reconstructing the actual LIS needs parent pointers.

• ✗Arrays.binarySearch with duplicates

  Symptom: an arbitrary matching index rather than the boundary you wanted.

  Prevention: Write your own lowerBound / upperBound.

• ✗Forgetting to decode a negative return

  Symptom: a negative number used directly as an index.

  Prevention: if (i < 0) i = -(i + 1);

• ✗Using lowerBound for a non-strict LIS

  Symptom: equal elements are treated as unable to extend, so the length comes out short.

  Prevention: Non-strict wants upperBound semantics.