Binary Search: One Invariant to Rule the Search Space

You think you know binary search. You've written it a dozen times. Then you sit in an interview, implement it from scratch, and ship a subtle bug that causes an infinite loop or silently returns the wrong answer. This happens to engineers who have been coding for years. It will happen again.

The algorithm is seven lines. The loop invariant is one statement. The tricky part: that statement is easy to believe you understand while you actually don't. Seven lines and four different ways to be confidently wrong.

This is the reference you reach for when you want to get it exactly right.

What Binary Search Actually Is

Binary search finds a target in a sorted array in O(log n) time by maintaining a shrinking interval. At every step, it compares the target to the middle element, then discards the half that cannot contain the target. The interval halves each iteration, so after at most log2(n) + 1 steps, it has either found the target or proved it is absent.

The mental model: you are not scanning, you are asking yes/no questions about which half the answer lives in.

That framing generalizes far beyond sorted arrays. Any problem where you can ask a binary yes/no question whose answers are monotone (all "no" then all "yes", or all "yes" then all "no") admits binary search. This is where the real power is, and most engineers miss it.

Each step halves the search space. Three comparisons, ten elements. After seven it's down to one.

State the Invariant Before You Code

The loop invariant is a statement that is true at the start of every loop iteration. Get it wrong and you get off-by-one errors. Get it inconsistent and you get infinite loops. The invariant is the design of the algorithm, not a comment you write after the fact.

There are two common styles. Pick one and stick with it. Do not mix them in the same function unless you enjoy debugging infinite loops at 11pm.

Style 1: Closed interval [lo, hi]

Invariant: if the target exists in the array, it lies in arr[lo..hi] (both endpoints inclusive).

lo = 0, hi = n - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        lo = mid + 1   # mid ruled out, search right
    else:
        hi = mid - 1   # mid ruled out, search left
return -1

When the loop exits with lo > hi, the invariant says the target is not present.

Style 2: Half-open interval [lo, hi)

Invariant: if the target exists, it lies in arr[lo..hi-1], i.e., lo is inclusive, hi is exclusive.

lo = 0, hi = n
while lo < hi:
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        lo = mid + 1   # exclude mid and everything left
    else:
        hi = mid       # exclude everything from mid right
return -1

When the loop exits with lo == hi, the interval is empty.

The half-open style has one advantage: it maps directly onto the lower-bound and upper-bound variants without changing any logic. More on that shortly.

![Side-by-side comparison of closed interval [lo,hi] and half-open interval lo,hi) with init conditions, loop conditions, and shrink rules The rules are not interchangeable. hi = mid is correct in half-open. hi = mid in closed style will loop forever when lo + 1 == hi.

Why It Always Terminates

The termination argument rests on one fact: when lo < hi, the formula mid = lo + (hi - lo) // 2 guarantees lo <= mid < hi. Integer division rounds down. When hi = lo + 1, mid = lo. When hi = lo + 2, mid = lo + 1. The strict upper bound mid < hi always holds.

• In the closed-interval style, setting lo = mid + 1 advances lo past mid, and hi = mid - 1 retreats hi below mid. Either way, hi - lo strictly decreases.
• In the half-open style, setting lo = mid + 1 advances lo, and hi = mid retreats hi (since mid < hi). Same guarantee.

Every branch strictly shrinks the interval. The interval is bounded below by zero. Therefore, the loop terminates.

The 20-Year Overflow Bug Nobody Noticed

For decades, the standard implementation computed mid = (lo + hi) / 2. In Java's Arrays.sort, this lived undetected for over 20 years before Joshua Bloch wrote about it in 2006. Twenty years. Millions of JVMs. Nobody noticed. When lo and hi are both close to INT_MAX (2,147,483,647 on 32-bit), their sum overflows to a negative number, and mid becomes wrong.

The fix is mid = lo + (hi - lo) / 2. The difference hi - lo fits in range (it is at most the array length), and adding lo back cannot overflow if the array fits in memory.

In Python this is moot because integers have arbitrary precision. In Rust, arithmetic overflow panics in debug mode and wraps in release mode. In C and C++, signed integer overflow is undefined behavior. In Java, Go, and C#, it wraps silently. Always use the safe formula.

What Every Operation Costs

All of these are worst-case, not amortized. Binary search on a sorted array always runs in O(log n). There is no averaging argument needed. The interval halves every step, deterministically.

The space cost is O(1) for the iterative version. A recursive formulation adds O(log n) stack frames, which is rarely a concern but worth knowing.

Lower Bound vs. Upper Bound: One Character Apart

These are the two most important variants. They are almost identical.

Lower bound finds the first index where arr[i] >= target. If all elements are less than target, it returns n (one past the end). This matches Python's bisect.bisect_left and C++'s std::lower_bound.

Upper bound finds the first index where arr[i] > target. If all elements are less than or equal to target, it returns n. This matches Python's bisect.bisect_right and C++'s std::upper_bound.

# Lower bound: first index where arr[i] >= target
def lower_bound(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

# Upper bound: first index where arr[i] > target
def upper_bound(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo

The only difference between lower and upper bound is < versus <= in the comparison. That one character changes which equal elements get included in the left half. One character. Infinite confusion. This is fine.

To count occurrences of target in a sorted array: upper_bound(arr, target) - lower_bound(arr, target). To check presence: lower_bound(arr, target) < n and arr[lower_bound(arr, target)] == target.

lower_bound lands on the first match. upper_bound lands on the first element past the last match. Their difference is the count.

The invariant for lower/upper bound

For lower bound, the invariant is:

• Everything in arr[0..lo-1] is strictly less than target
• Everything in arr[hi..n-1] is greater than or equal to target

When the loop exits with lo == hi, that index is the first position where the condition holds.

For upper bound, swap the boundary condition: everything in arr[0..lo-1] is less than or equal to target.

This is why hi starts at n (not n-1). The answer might be n when no element satisfies the condition, and the half-open range [lo, hi) naturally includes that case.

Binary Search on Answer

This is the leap from "search for a value" to "search for the boundary where a property flips." It is where binary search stops being a lookup primitive and becomes a design pattern. Most engineers know the first kind. Interviewers ask about the second kind.

The idea: suppose you cannot directly compute the optimal value of some parameter, but you can efficiently check whether a given value is feasible. If feasibility is monotone (once it becomes feasible, it stays feasible as the parameter increases), you can binary search over the answer space.

The whole search space looks like this. Binary search finds the transition in O(log n) no matter how wide the range.

The template for "find the minimum value that satisfies the predicate":

def binary_search_on_answer(lo: int, hi: int, feasible) -> int:
    # Precondition: feasible(hi) is True
    # Returns: smallest x in [lo, hi] where feasible(x) is True
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid       # mid might be the answer, keep it
        else:
            lo = mid + 1   # mid definitely not the answer, exclude it
    return lo

For "find the maximum value that satisfies the predicate," invert: lo = mid + 1 when feasible, hi = mid otherwise, and return lo - 1 after the loop (or return hi from the last feasible branch).

Worked example: Koko Eating Bananas

Koko has piles of bananas. She has h hours. She eats at speed k bananas per hour (one pile per hour, at most k from that pile). Find the minimum k that lets her finish in h hours.

def min_eating_speed(piles: list[int], h: int) -> int:
    def can_finish(speed: int) -> bool:
        return sum((pile + speed - 1) // speed for pile in piles) <= h

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_finish(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The feasibility predicate can_finish(speed) is monotone: if speed k works, any speed k' > k also works (she finishes faster). So the answer space has the shape [False, False, ..., True, True], and binary search finds the leftmost True in O(n log(max_pile)) time.

Worked example: Split Array Largest Sum

Divide an array into exactly k non-empty contiguous subarrays to minimize the maximum subarray sum.

def split_array(nums: list[int], k: int) -> int:
    def can_split(limit: int) -> bool:
        parts, current = 1, 0
        for num in nums:
            if current + num > limit:
                parts += 1
                current = 0
            current += num
        return parts <= k

    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if can_split(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

The search space is [max(nums), sum(nums)]. The lower bound is max(nums) because the largest single element must fit in some subarray. The upper bound is sum(nums) because one subarray containing everything always works.

What Problems It Solves

Binary search applies to three broad categories.

Direct search in sorted data. Finding an element, counting occurrences, finding the nearest value, or checking membership. These problems give you the sorted array explicitly.

"First true" problems. Given a predicate that transitions from false to true exactly once on some range, find the transition point. Finding the first bad version in a sequence of commits. Finding the minimum feasible threshold. These feel like search problems but the "array" is implicit.

Monotone optimization. "Minimize the maximum," "maximize the minimum," or "find the smallest parameter such that some constraint is satisfiable." These require the insight that you can reframe the optimization as a feasibility check, then binary search over the answer space.

Recognizing the Pattern

The signals that a problem calls for binary search are reasonably concrete.

In a sorted array: you want something faster than O(n). The structure is already there.

"Minimize the maximum" or "maximize the minimum": this phrasing almost always means binary search on the answer. The words are a near-direct translation of the monotone structure. "Minimize the maximum" means the feasibility check is "can we achieve maximum <= x?", which gets easier as x increases.

You can answer a yes/no version faster than the original: if the problem asks for an optimal value but you can quickly check whether a candidate value is achievable, binary search on the answer.

The output is a threshold, not a specific element: problems like "how many ships can load in D days?", "what is the minimum capacity to deliver packages?", "at what point does the function first exceed zero?"

Example 1: LeetCode 875 (Koko Eating Bananas)

Problem: piles of bananas, h hours, eat one pile per hour at at most k bananas, find minimum k.

Why binary search: the answer k ranges from 1 to max(piles). Feasibility (can she finish in h hours?) is monotone in k. Single-pass greedy feasibility check is O(n). Total: O(n log(max_pile)).

Example 2: LeetCode 1011 (Capacity to Ship Packages)

Problem: packages with weights arrive in order over d days, find minimum ship capacity to send all packages within d days.

Why binary search: capacity ranges from max(weights) to sum(weights). The feasibility check (can we ship all packages in d days at this capacity?) is a single left-to-right greedy pass. The predicate is monotone. Binary search on [max, sum] gives O(n log(sum - max)).

Example 3: LeetCode 33 (Search in Rotated Sorted Array)

Not binary-search-on-answer, but a subtler invariant. One half of a rotated array is always sorted. You can determine which half with one comparison, then apply standard binary search logic to the sorted half. The invariant becomes: at every step, identify the sorted half and check if the target lies within it.

One Structure, Every Language

All implementations below assume a sorted input array. Lower bound returns the first index where arr[i] >= target. The exact search returns the index of the target or -1 if absent.

from bisect import bisect_left

def lower_bound(arr: list[int], target: int) -> int:
    return bisect_left(arr, target)

def binary_search(arr: list[int], target: int) -> int:
    index = bisect_left(arr, target)
    if index < len(arr) and arr[index] == target:
        return index
    return -1

# Manual implementation showing the invariant
def binary_search_manual(arr: list[int], target: int) -> int:
    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

The Off-by-One Hall of Shame

Off-by-one errors are, famously, one of the hardest things in computer science.

Yes, the numbering on that list is part of the joke. If you had to read this caption to get it, you may be in trouble.

Before you write this in an interview, know the failure modes.

Wrong loop condition. Using lo < hi with a closed interval [lo, hi] will miss the element when lo == hi. The interval still contains one candidate. Use lo <= hi for closed intervals or lo < hi for half-open.

Not narrowing on a hit. If you write lo = mid instead of lo = mid + 1 in the exact-search version, and the target is at mid, the loop runs forever. Every branch must strictly move lo or hi.

Wrong initial hi. For exact search with a closed interval, hi = n - 1. For lower/upper bound with a half-open interval, hi = n. These are not interchangeable.

Mixing styles. Deciding hi = mid in one branch and hi = mid - 1 in another branch of the same function is a bug. Pick one style and be consistent throughout.

Checking predicate on stale state. In binary-search-on-answer, after the loop lo == hi. That is your answer. Do not call feasible(lo) again to double-check unless you enjoy paying an extra O(n) for the privilege of confusing yourself.

If you practice binary search with SpaceComplexity, the voice interview will push you to explain the invariant aloud, which surfaces these errors before they cost you an offer.

The Searchable Property Is the Insight

Binary search is not an algorithm about sorted arrays. It is an algorithm about monotone predicates. The sorted array is just the most common case where the predicate (is this element the target?) happens to be monotone.

When you see a problem that involves searching for a threshold, or optimizing under a constraint, or asking "at what point does this property hold?", think about what the yes/no question is and whether it is monotone. If it is, you have a binary search. If the question can be answered in O(n), the binary search gives you O(n log n) total. That is usually fast enough.

The hard part is not the implementation. It is the translation: recognizing that an optimization problem is secretly a monotone feasibility problem. Once you see it, the code writes itself. Getting there just requires staring at the problem for longer than feels comfortable.

For more on recognizing algorithmic patterns in interview problems, see the sliding window algorithm and the dynamic programming framework, both of which follow a similar "recognize the shape first" approach.

Recap

• The invariant is the algorithm. Write down what [lo, hi] means before you write the loop.
• Use mid = lo + (hi - lo) / 2 to avoid overflow in languages with fixed-size integers.
• Lower bound finds the first index where arr[i] >= target. Upper bound finds the first index where arr[i] > target. They differ by one character.
• Binary search on answer: identify the search space, define the monotone feasibility predicate, binary search on [min_answer, max_answer].
• "Minimize the maximum" and "maximize the minimum" are near-certain signals for binary search on answer.
• Every branch must strictly shrink the interval. Any branch that sets hi = mid when hi could equal mid causes an infinite loop.
• After the loop in lower/upper bound or binary-search-on-answer, lo == hi and that is your answer. Trust the invariant.

Further Reading

• Binary search algorithm (Wikipedia), comprehensive treatment including history and the correctness proof
• bisect module (Python docs), official documentation for Python's lower/upper bound functions
• Binary Search Functions in C++ STL (GeeksforGeeks), lower_bound, upper_bound, and binary_search with examples
• Binary Search Tutorial (cp-algorithms), the invariant-first derivation and the search-on-predicate generalization
• Binary Search on Answer (GeeksforGeeks), worked problems with the feasibility-check pattern
• slice::binary_search (Rust docs), Rust's binary_search, partition_point, and their semantics