Binary Search Problems: 11 That Cover Every Interview Pattern

Every binary search problem you'll see in a coding interview is wearing a costume. Strip off the costume and there are exactly three shapes underneath. The trouble is that most engineers practice one shape, check "binary search" off the prep spreadsheet, and then blank on LeetCode 33 when the array is rotated or LeetCode 875 when there's no array to search in the first place.

These 11 problems, ordered easy to hard, collectively teach every binary search idea that actually shows up at interviews. Work through them in order and you're not memorizing solutions. You're building a framework that extends to problems you've never seen.

Memorize These Three Templates First. Seriously.

Internalize these before problem one. Everything else is a costume worn over one of them.

Template 1: exact match

lo, hi = 0, len(arr) - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: lo = mid + 1
    else: hi = mid - 1
return -1

Template 2: leftmost boundary

lo, hi = 0, len(arr)        # hi = len, not len-1
while lo < hi:               # strict <
    mid = lo + (hi - lo) // 2
    if condition(mid): hi = mid
    else: lo = mid + 1
return lo

Template 3: binary search on the answer space

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

Here's where 90% of candidates quietly lose it: the boundary conditions. hi = len - 1 vs hi = len, and lo <= hi vs lo < hi are not cosmetic differences. They are not interchangeable. They change what the loop invariant guarantees when the loop exits. Write the wrong one and you get a wrong answer on a test case that definitely should have worked, and you'll have no idea why.

Also: lo + (hi - lo) // 2, not (lo + hi) // 2. The second form overflows a 32-bit integer when both are large. Java's standard library shipped this bug for nine years. Yes, really.

Off-by-one errors in binary search: they only appear when lo and hi are both large, or on edge cases, or when your interviewer is watching.

1. Binary Search (LC 704)

Difficulty: Easy. What it teaches: the base template and nothing else.

Write it from memory right now. Then check: did you write Template 1 exactly, or did you introduce a subtle variation that will haunt you later? The invariant is that the target, if it exists, lives in [lo, hi]. When that range collapses to empty, it's not there. That invariant is the whole algorithm. Internalize it before moving on.

2. Search Insert Position (LC 35)

Difficulty: Easy. What it teaches: what lo means when you don't find anything.

No match, and you return lo. The loop maintained the invariant that the insertion point lives in [lo, hi]. When lo = hi + 1 and the range is empty, lo is the first index where arr[lo] >= target. That's the insertion point, and this fact appears in dozens of harder problems. This problem makes it concrete and unambiguous.

3. First Bad Version (LC 278)

Difficulty: Easy. What it teaches: binary search on a predicate, not a value.

The array isn't given to you. You have isBadVersion(v) returning true or false. Versions go [good, good, ..., bad, bad, bad] and you want the first bad one.

This is Template 2 in its purest form. You're not searching for a number. You're searching for the first position where a boolean condition flips from false to true. Every "binary search on the answer" problem later in this list is secretly this problem, just with a more expensive condition function. Get the template clean here.

4. Find First and Last Position (LC 34)

Difficulty: Medium. What it teaches: two separate passes with opposite biases.

One pass finds the leftmost occurrence, another finds the rightmost. Leftmost is standard Template 2: when arr[mid] == target, move hi = mid. Rightmost flips: when arr[mid] == target, move lo = mid + 1, then return lo - 1.

Two focused passes with different biases are cleaner, more testable, and easier to reason about under pressure than any attempt to handle both in one loop. Resist the urge to be clever.

5. Find Minimum in Rotated Sorted Array (LC 153)

Difficulty: Medium. What it teaches: comparing against arr[hi] instead of a target.

No target. You want the inflection point where the rotation broke the sorted order. The key move: compare arr[mid] to arr[hi]. If arr[mid] > arr[hi], the minimum is in the right half. Otherwise it's in the left half, including mid itself.

Why arr[hi] and not arr[lo]? Because arr[lo] could be larger than arr[mid] when the rotation is big, giving you nothing useful. arr[hi] is always a stable reference point. This comparison strategy shows up again in problem 6.

6. Search in Rotated Sorted Array (LC 33)

Difficulty: Medium. What it teaches: identify which half is sorted, then decide where the target could be.

This builds directly on problem 5. With a target, you first determine which half is cleanly sorted (using the arr[lo] vs arr[mid] vs arr[hi] comparisons from the previous problem), then check whether the target falls in that sorted half's range. Yes, search there. No, search the other half.

The two-step approach, identify sorted half first then decide, is cleaner and stays correct under pressure. Don't try to construct a single comparison that handles all cases. You won't.

7. Time Based Key-Value Store (LC 981)

Difficulty: Medium. What it teaches: binary search as a subroutine inside a larger system.

Each key maps to a list of (timestamp, value) pairs. You need the most recent value at or before a given timestamp. That's a "rightmost position where timestamp <= query" search on the timestamp list for a given key.

The real skill here is recognizing where binary search fits inside a larger design. This problem doesn't look like a search problem on the surface. It looks like a design problem. That's the point.

8. Find Peak Element (LC 162)

Difficulty: Medium. What it teaches: binary search on an array with no sorted guarantee.

The array isn't sorted, yet binary search works. From any mid, check the gradient: if arr[mid] < arr[mid + 1], a peak exists to the right. Otherwise one exists to the left or at mid. Move uphill.

This is binary search as gradient descent. You're not eliminating half the space because you know where the target is. You're eliminating it because moving in one direction guarantees convergence toward a valid answer. That's a more general idea than the basic template.

9. Koko Eating Bananas (LC 875)

Difficulty: Medium. What it teaches: Template 3, binary search on the answer space.

The array isn't what you're searching. You're searching for the minimum eating speed k such that Koko finishes all piles within h hours. The answer lives in [1, max(piles)]. For each candidate speed, the feasibility check is O(n): sum(ceil(pile / k) for pile in piles) <= h.

Before applying Template 3, always verify monotonicity: if speed k works, then k + 1 also works. That's true here. Without monotonicity, binary search gives you wrong answers with no error message, and you'll waste 20 minutes wondering why. State the monotone argument before you code it.

Applying Template 3 vs. figuring out why your greedy feasibility function counts k+1 pieces instead of k.

10. Split Array Largest Sum (LC 410)

Difficulty: Hard. What it teaches: a non-trivial greedy check inside the answer space template.

Minimize the maximum subarray sum when splitting an array into exactly k subarrays. Binary search on the answer (the maximum allowed sum per subarray). The feasibility check: can you partition into at most k pieces where no piece exceeds the limit?

That check is a greedy scan. Greedily extend each subarray until adding the next element would exceed the limit, start a new piece, count pieces, check whether you stayed within k. The binary search structure is automatic by now. What's actually being tested is whether you can write a clean greedy feasibility function under pressure and wire it correctly into the outer template. Practice Koko first. By this problem, the outer loop should require no thought.

11. Median of Two Sorted Arrays (LC 4)

Difficulty: Hard. What it teaches: binary search for a structural invariant, not a value.

Binary search for the correct number of elements taken from the first array to form the left half of the combined sorted array. For each candidate partition position, check the invariant across the four boundary elements: maxLeft1 <= minRight2 and maxLeft2 <= minRight1. Adjust left or right based on which constraint is violated.

You're not searching for a value at all. You're binary searching for a position that satisfies a structural invariant across two arrays simultaneously. This is the hardest mental model in the set. If you study only one hard binary search problem end to end, make it this one. The partition-based thinking transfers to problems that look nothing like search problems.

All 11, Mapped

Problem	LC	Template	Core Insight
Binary Search	704	Exact match	Base template, overflow
Search Insert Position	35	Leftmost	`lo` = insertion point
First Bad Version	278	Leftmost	Predicate, not value
First and Last Position	34	Leftmost x2	Two passes, opposite bias
Find Minimum Rotated	153	Leftmost	Compare to `arr[hi]`
Search in Rotated	33	Exact match	Identify sorted half first
Time Based KV Store	981	Rightmost	BS as subroutine
Find Peak Element	162	Gradient	Move toward slope
Koko Eating Bananas	875	Answer space	Monotone feasibility
Split Array Largest Sum	410	Answer space	Greedy feasibility check
Median Two Sorted Arrays	4	Partition	Binary search on cut

Every new binary search problem you encounter maps to one of these rows. When you see a new problem, your first question is: am I searching for a value, a boundary, an optimal parameter, or a partition?

Three Templates Are All You Need

Three templates cover everything. Exact match, leftmost boundary, answer space.
The off-by-one differences between templates are not cosmetic. lo <= hi vs lo < hi and hi = len - 1 vs hi = len change what the loop guarantees on exit.
Binary search on the answer space requires a monotone feasibility predicate. State the monotone argument before you code. If you can't state it, the template doesn't apply.
Problems 5, 8, and 11 teach that binary search doesn't need a target value. It only needs a direction rule.
Median of Two Sorted Arrays is worth slow, deliberate study. The partition-based thinking transfers.

Once you can solve all 11 from memory in under 20 minutes each, you've internalized binary search to the depth interviews actually probe. SpaceComplexity runs voice-based mock interviews that put you through these under real timing pressure, then scores whether you explained the invariant before you coded, not just whether the output was correct.