Binary Search Template — Recognition, Boundary Rule, Three Walkthroughs

Binary search is one line of code and three subtle bugs. The line is easy. The bugs — off-by-one, infinite loop, wrong boundary — are what make interviewers ask you to write it on a whiteboard. Learn one template that avoids all three and the technique becomes a tool you can carry to problems that don't look like sorted-array lookups at all.

Recognition — when to reach for it

Binary search is the right tool when all three of these hold:

There's a search space — an array of indices, a range of values, a time budget — that you're picking one element from.
There's a monotone predicate over that space: as you move in one direction, the predicate flips from false to true (or vice versa) exactly once.
Evaluating the predicate at any point is cheaper — usually O(1) or O(n) — than scanning the whole space linearly, which would be O(space size).

The first two are the load-bearing conditions. If the predicate isn't monotone, halving the space doesn't safely eliminate anything. If there's no search space, there's nothing to bisect.

The most surprising thing about binary search is that the search space does not have to be an array. Any monotone predicate over any range of integers or floats will do — capacity, speed, time, k for k-th smallest. That opens up a whole class of "optimisation" problems that look like they need DP or greedy but really need binary search on the answer domain.

Mental model — why it collapses to O(log n)

You've cut the search space in half. Then you cut the remaining half in half. Then again. After log₂(n) cuts, only one candidate remains, and it's the answer. n = 1M shrinks to 20 cuts. n = 4B shrinks to 32.

Each cut has to be safe: whichever half you throw away, you're certain the answer isn't in it. Safety comes from the monotone predicate. If predicate(mid) is true and the predicate is monotonically flipping from false → true, then everything to the right of mid (in a false → true monotone) is also true, so mid might already be the boundary — the answer is in [left, mid], and you can safely drop (mid, right]. Reverse the halving if the predicate flips the other way.

The two templates

Every binary search resource on the internet starts with what's usually called the "classic" template:

def binary_search_classic(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

This works for exact-match on a sorted array and nothing else. If the target isn't present, or if you want the leftmost/rightmost occurrence, or if you're searching a value space instead of an index space, you'll write three subtly different versions of this and one of them will have an infinite loop.

Learn the boundary template instead. It solves every binary search problem, and its shape is identical every time:

def find_boundary(low: int, high: int, predicate) -> int:
    # Returns the smallest x in [low, high) with predicate(x) == True,
    # or `high` if no such x exists. `predicate` must be monotone:
    # once True at some x, True for every x' > x.
    while low < high:
        mid = low + (high - low) // 2
        if predicate(mid):
            high = mid
        else:
            low = mid + 1
    return low

Four invariants make this template bug-proof:

high is exclusive. The search space is [low, high). This is what makes "no match" naturally return high (one past the end) instead of needing a special case.
Loop while low < high, not low <= high. With inclusive bounds you need to shrink both sides on every iteration, which is where infinite loops come from.
mid = low + (high - low) // 2, never (low + high) // 2. The extra care is for languages where the sum can overflow. In Python this doesn't happen, but the habit ports to Java, C++, and Go for free.
On the "true" branch, high = mid (not mid - 1). mid might be the answer; don't discard it. On the "false" branch, low = mid + 1 — mid is known bad, safe to skip.

Every binary search problem in this post reduces to: define the predicate, call find_boundary. Even the "classic" exact-match becomes a boundary search — find the smallest index where nums[i] >= target, then verify nums[low] == target.

The killer insight — binary search on the answer

The search space doesn't have to be an array. It can be the domain of possible answers.

If the question is "what's the smallest / largest X such that we can achieve some goal?" and the "can we?" predicate is monotone in X, then binary search finds X in log(max X) predicate evaluations. Each predicate might itself take O(n) — so the total is O(n log(max X)), which is nearly always what you want when the answer space is numeric.

LC 1011 (Capacity To Ship Packages Within D Days), LC 875 (Koko Eating Bananas), LC 410 (Split Array Largest Sum), and LC 4 (Median of Two Sorted Arrays) all reduce to this shape. It's the single biggest unlock in the technique.

Walkthrough 1 — LeetCode 704, Binary Search

Given a sorted array nums and a target, return the index of target, or -1 if not present.

Recognition. Sorted array (predicate nums[i] >= target is monotone in i). Search space is [0, n). Predicate is O(1). Textbook.

Predicate. nums[i] >= target.

def search(nums: list[int], target: int) -> int:
    low, high = 0, len(nums)
    while low < high:
        mid = low + (high - low) // 2
        if nums[mid] >= target:
            high = mid
        else:
            low = mid + 1
    # low is the leftmost index with nums[low] >= target,
    # or len(nums) if all elements are < target.
    return low if low < len(nums) and nums[low] == target else -1

Trace nums = [-1, 0, 3, 5, 9, 12], target = 9.

low	high	mid	numsmid	predicate	action
0	6	3	5	5 ≥ 9? no	low = 4
4	6	5	12	12 ≥ 9? yes	high = 5
4	5	4	9	9 ≥ 9? yes	high = 4

Loop exits with low = 4. nums[4] == 9, return 4. Three predicate checks for a six-element array — that's the log₂(6) ≈ 2.6 collapse.

Walkthrough 2 — LeetCode 153, Find Minimum in Rotated Sorted Array

A sorted ascending array has been rotated at an unknown pivot. Return the minimum. No duplicates.

Recognition. Not sorted globally, but has a monotone structure hidden inside: every element to the right of the pivot is smaller than every element to the left. That's monotone enough for binary search.

Predicate. nums[i] <= nums[-1]. Everything from the pivot onward satisfies this; everything before it doesn't. The minimum is the leftmost index where the predicate flips to true.

def findMin(nums: list[int]) -> int:
    low, high = 0, len(nums) - 1  # inclusive here — we return nums[low]
    while low < high:
        mid = low + (high - low) // 2
        if nums[mid] > nums[high]:
            # Pivot is to the right of mid — minimum is in (mid, high].
            low = mid + 1
        else:
            # nums[mid] <= nums[high] — mid could be the minimum.
            high = mid
    return nums[low]

Why compare nums[mid] to nums[high] and not nums[low]? Because on a non-rotated (sorted) input, nums[mid] < nums[low] never fires — the predicate against low isn't monotone. Comparing against high handles rotated and sorted inputs uniformly, which is exactly the invariant we want.

Trace nums = [4, 5, 6, 7, 0, 1, 2].

low	high	mid	numsmid	numshigh	action
0	6	3	7	2	7 > 2, low = 4
4	6	5	1	2	1 ≤ 2, high = 5
4	5	4	0	1	0 ≤ 1, high = 4

Return nums[4] = 0. The predicate did the work of "find the pivot" without ever needing to compute the pivot explicitly.

Note the high = len(nums) - 1 here (inclusive) — because the answer is nums[low], not low itself, and we need low to land on a valid index. This is a fair use of the inclusive form; the general boundary template's exclusive form is for when the "no answer" case naturally exists.

Walkthrough 3 — LeetCode 1011, Capacity To Ship Packages Within D Days

A conveyor belt has weights in order. Each day you can load a contiguous prefix onto the ship as long as the load stays under the ship's capacity. Return the smallest capacity that ships everything within days days.

Recognition. Optimisation. Not obviously a search problem. But the predicate "can we ship in days days with capacity C?" is monotone in C — if you can do it with C, you can do it with C + 1 (any partition that works at C still works at C + 1). That's the binary-search-on-answer signal.

Search space. [max(weights), sum(weights)]. The lower bound is max(weights) because any capacity smaller than the biggest package can't even load that one package. The upper bound is sum(weights) because with capacity equal to the total, we ship everything in one day.

Predicate. Greedy simulation. Walk the weights, filling the day's ship until adding the next weight would exceed capacity, then start a new day. Return true if we used at most days days.

def shipWithinDays(weights: list[int], days: int) -> int:
    def can_ship(capacity: int) -> bool:
        used_days = 1
        current = 0
        for w in weights:
            if current + w > capacity:
                used_days += 1
                current = 0
            current += w
        return used_days <= days

    low, high = max(weights), sum(weights) + 1  # exclusive upper
    while low < high:
        mid = low + (high - low) // 2
        if can_ship(mid):
            high = mid
        else:
            low = mid + 1
    return low

Complexity: O(n × log(sum − max)). Each predicate call is O(n); we do log₂ of the search space many calls. For weights = [1..50000] with sum ≈ 1.25e9, that's about 30 predicate calls total — fast.

Sketch of weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], days = 5.

Search space [10, 56).
mid = 33: can_ship(33) uses 2 days — plenty of headroom → high = 33.
mid = 21: can_ship(21) uses 3 days → high = 21.
mid = 15: can_ship(15) uses 5 days — exactly at the limit → high = 15.
mid = 12: can_ship(12) uses 6 days → low = 13.
mid = 14: can_ship(14) uses 6 days → low = 15.
low == high == 15, loop exits.

Return 15. Five predicate evaluations to explore a 46-value search space, each predicate O(n). Against a linear scan of the capacity range that lacks the monotone-predicate reasoning, the win is roughly log(range) / range — an order of magnitude on this input, and it grows as the range does.

Common pitfalls

The boundary template deletes most of them, but three are worth naming so you can recognise them in someone else's code:

Integer overflow. (low + high) // 2 overflows in fixed-width integer languages when low + high exceeds the max int. low + (high - low) // 2 avoids it. Free habit; adopt it in Python too so it ports.
left = mid on the false branch. If the predicate is false at mid and you set left = mid instead of left = mid + 1, and high = left + 1, the loop stops making progress — infinite loop. low = mid + 1 on false, high = mid on true is the incantation.
Inclusive vs exclusive drift. Mixing high = len(nums) with while low <= high runs off the end. Mixing high = len(nums) - 1 with high = mid when nothing satisfies the predicate returns the wrong index. Pick a convention per problem (exclusive for the general template, inclusive when the return value indexes into the array) and stick with it inside the function.

When binary search is not the tool

No monotone predicate. Unsorted array with no derivable monotone structure. Reach for a hash map, or sort first if you can afford the O(n log n).
You need every match, not one. Binary search finds a boundary. If you need to enumerate all occurrences, binary-search the leftmost and rightmost occurrence, then iterate between them.
The predicate is too expensive. If each predicate call is O(n²) and the search space is n, you've built an O(n³ log n) algorithm — probably worse than the O(n²) direct solution.
The answer is trivially computable in O(n) with a linear scan. LC 121 (Best Time to Buy and Sell Stock) has an O(n) running-min solution; binary-searching it is a resume flex, not an improvement.

How the Algotrek tutor would prompt you here

When a learner opens a binary-search problem on Algotrek, the tutor doesn't reveal the template. It asks three questions, and only advances when each is answered in one sentence:

"What is the search space?" — Forces the learner to name what they're bisecting. An index range? A capacity range? A time budget? Naming it out loud is what turns "binary search" from a memorised pattern into a tool that transfers to LC 1011.
"What is the monotone predicate over that space?" — This is the whole trick. "nums[i] >= target" for LC 704. "nums[i] <= nums[high]" for LC 153. "can_ship(capacity)" for LC 1011. If you can't articulate the predicate, you're not ready to code.
"Do you want the boundary between predicate-false and predicate-true, or an exact match?" — Boundary is the general answer; exact match is a boundary plus a post-hoc equality check. Once you internalise this, the "two templates" collapse into one.

Answer all three and the loop is a five-line typing exercise. Try the Binary Search lesson on Algotrek to see the prompt-then-reveal flow on the archetypal problem, then step up to the Find Minimum in Rotated Sorted Array lesson to feel the predicate framing pay off on a problem that doesn't look bisectable.

Where to go next

LC 875, Koko Eating Bananas. The canonical binary-search-on-answer problem. If LC 1011 clicked, this is the same shape with a slightly different predicate — and Algotrek's lesson walks the "guess the search space bounds" step that trips most learners.
LC 33, Search in Rotated Sorted Array. LC 153 plus target lookup. The predicate takes more care because the target might be on either side of the pivot. A good sanity check that you've internalised the "compare against high" invariant.
LC 410, Split Array Largest Sum. Binary search on answer, boss level. Same shape as LC 1011 — if you can spot that reduction in an interview, you'll write it in half the time of anyone reaching for DP.
LC 4, Median of Two Sorted Arrays. Binary search on the partition point, not the value. Hard, and worth grinding once you own the boundary template — it's the interview problem where "you can't do this without binary search" is most obviously true.

Cross-reference the sliding-window and two-pointer posts. All three techniques are about reasoning over an invariant that lets you skip work you don't have to do — sliding window on a contiguous range, two-pointer on a converging pair, binary search on a bisectable space. Recognising which invariant a problem hands you is the meta-skill; the templates just cash it in.

The Big-O cheat sheet covers the amortised-O(1) hash-map ops the walkthroughs above assume, plus the O(log n) row that every binary-search variant cashes in on.