Binary search

Find a target in a sorted array, or report that it is absent.

Trigger

'Sorted array' plus 'find'.

Approach

1. Use the half-open template every single time: lo = 0, hi = len(a), while lo < hi.
2. Say the invariant: if the target exists, it lies in [lo, hi).
3. Say the termination argument: hi − lo strictly decreases.

Target complexity

O(log n) time, O(1) space.

Pitfall

Improvising the bounds. Every off-by-one in binary search comes from not using one fixed template.

Say it out loud

“I'll use the half-open template, which is the one I always use so I don't introduce an off-by-one. The invariant is that if the target exists it's inside the current window, and the window strictly shrinks, so the loop terminates.”

Solve on LeetCode

Find the smallest ship capacity that ships all packages, in order, within D days.

Trigger

The same shape as Koko: 'smallest capacity that makes it possible'.

Approach

1. Recognise it immediately as binary search on the answer.
2. Lower bound is the largest single package (it must fit); upper bound is the total.
3. The predicate is a greedy simulation: pack until it overflows, then start a new day.
4. Verify monotonicity: more capacity never needs more days.

Target complexity

O(n log(sum)) time, O(1) space.

Pitfall

Setting the lower bound to 1. A capacity below the largest package can never work, and the greedy check would loop.

Say it out loud

“Same shape as Koko Eating Bananas — I'm binary searching the answer, and the check is a greedy packing simulation. The lower bound has to be the largest single package, since anything less can't ship it at all.”

Solve on LeetCode

Find the first and last index of a target in a sorted array with duplicates.

Trigger

'First and last occurrence', 'range of a value'.

Approach

1. Two binary searches: lower bound (first index >= target) and upper bound (first index > target).
2. Both use the same template with a different predicate — say that, it shows the template is understood.
3. If lower == upper the target is absent.

Target complexity

O(log n) time, O(1) space.

Pitfall

Finding one occurrence and then scanning linearly for the boundaries — that is O(n) in the worst case.

Say it out loud

“Two binary searches with the same template and different predicates: lower bound and upper bound. Finding one match and scanning outwards would be linear if the array is all one value, which defeats the point.”

Solve on LeetCode

Find the smallest element in a sorted array that has been rotated.

Trigger

'Rotated sorted array'.

Approach

1. The invariant is broken in exactly one place, and that place is the minimum.
2. Compare a[mid] with a[hi]: if a[mid] > a[hi], the break is to the right, so lo = mid + 1.
3. Otherwise the break is at mid or to its left, so hi = mid.
4. Compare against hi, not lo — comparing with lo does not disambiguate.

Target complexity

O(log n) time, O(1) space.

Pitfall

Comparing a[mid] with a[lo]. It fails on an unrotated array; compare with a[hi].

Say it out loud

“There's exactly one place where the sorted order breaks, and that's the minimum. Comparing the midpoint against the right end tells me which half contains the break — comparing against the left end doesn't disambiguate, which is the subtle part.”

Solve on LeetCode

Find the smallest eating speed that finishes all the piles within h hours.

Trigger

'Smallest k such that it is possible' — binary search on the answer.

Approach

1. Name the pattern: I'm not searching the array, I'm searching the answer space.
2. The predicate: hours_needed(speed) <= h. Verify it is monotonic — faster is never worse.
3. Search over [1, max(pile)]. Each check is a linear pass.
4. Use ceiling division for the hours per pile.

Target complexity

O(n log(max pile)) time, O(1) space.

Pitfall

Floor division when computing hours per pile. A partial pile still costs a whole hour.

Say it out loud

“The array isn't what I'm searching — the answer is. The predicate 'can she finish at this speed' is monotonic, which is exactly what binary search needs, and checking one candidate is a linear pass. So it's n log of the maximum pile size.”

Solve on LeetCode

Search a matrix whose rows are sorted and where each row starts after the previous one ends.

Trigger

A sorted matrix with the global-ordering property.

Approach

1. Say the observation: reading row-major, the matrix is one sorted array.
2. So binary search over [0, m·n) and convert the index with divmod(mid, n).
3. If only the rows were sorted independently, it would be a staircase walk from the top-right in O(m + n) — mention the distinction.

Target complexity

O(log(m·n)) time, O(1) space.

Pitfall

Doing two binary searches (row then column) when one suffices, or assuming the global ordering when the problem only guarantees per-row sorting.

Say it out loud

“Because each row starts after the previous ends, the matrix is just a sorted array with a reshaped index. So one binary search over m times n, converting the midpoint with divmod. If only rows were sorted, I'd walk from the top-right corner instead, which is O(m plus n).”

Solve on LeetCode

Find a target in a rotated sorted array.

Trigger

'Rotated' plus 'find the value'.

Approach

1. At every midpoint, one of the two halves is guaranteed to be properly sorted. Identify which.
2. If the target lies inside that sorted half's range, search there; otherwise search the other.
3. Mention the follow-up: with duplicates the worst case degrades to O(n), because a[lo] == a[mid] == a[hi] tells you nothing.

Target complexity

O(log n) time, O(1) space — O(n) worst case with duplicates.

Pitfall

Not checking that the target is inside the sorted half's *range*, only which half is sorted.

Say it out loud

“At every step one half is fully sorted, and I can tell which by comparing the endpoints. If the target falls inside that half's range I go there, otherwise the other one. Worth flagging: with duplicates this degrades to linear, because equal endpoints stop being informative.”

Solve on LeetCode

Find the median of two sorted arrays in logarithmic time.

Trigger

Two sorted arrays plus an explicit O(log(m+n)) requirement.

Approach

1. Merging is O(m+n). Say it, then say why it does not meet the bound.
2. Reframe: I'm looking for a partition point, not an element.
3. Binary search the cut in the shorter array; the cut in the other is determined by the total.
4. The condition: maxLeftA <= minRightB and maxLeftB <= minRightA. Use ±infinity at the edges.

Target complexity

O(log(min(m, n))) time, O(1) space.

Pitfall

Binary searching the longer array, or forgetting the infinity sentinels at the boundaries.

Say it out loud

“The insight is that I'm not searching for a value, I'm searching for a partition: a cut in each array such that everything left is below everything right. Fixing one cut determines the other, so I binary search the shorter array. The sentinels at the edges are what keep the comparisons uniform.”

Solve on LeetCode

Split an array into k contiguous parts, minimising the largest part sum.

Trigger

'Minimise the maximum' — the strongest signal for binary search on the answer.

Approach

1. 'Minimise the maximum' is the trigger phrase. Say it.
2. Binary search the candidate maximum between max(a) and sum(a).
3. The check: greedily fill parts up to the candidate and count how many you needed — feasible if that count is at most k.
4. Mention the O(n²k) DP as the alternative, and why binary search is better here.

Target complexity

O(n log(sum)) time, O(1) space.

Pitfall

Going straight to DP. It is correct but much slower, and it misses the pattern the problem is testing.

Say it out loud

“'Minimise the maximum' is the phrase that tells me to binary search the answer. For a candidate maximum, greedily filling parts tells me how many I'd need, and that's monotonic in the candidate. There's a DP solution too, but it's n squared times k, and this is n log sum.”

Solve on LeetCode