Binary Search

TL;DR

Binary search is the algorithm you reach for whenever you can phrase the problem as: “I have a search space, and given any candidate x in it, I can cheaply tell whether the answer is in the left half or the right half.” Each step throws away half of what’s left, so a billion candidates collapse to about 30 probes.

Three flavors carry 95% of real use. Vanilla searches a sorted array for a target. lower_bound / upper_bound return the insertion point — the first index satisfying a predicate, which is what you want once duplicates exist. Search on answer binary-searches the answer space of an optimization problem (“smallest speed such that…”) whenever the feasibility check is monotone. Same scaffold, three job descriptions.

The picture in your head

Looking up a word in a paper dictionary. You don’t start at page 1 and read forward — you flip to the middle, see whether your word comes before or after, and throw the other half away. Repeat on the half that’s left. A 2,000-page dictionary is solved in about 11 flips because every flip cuts the unsearched range in half. The sorted ordering is the entire trick: it lets one comparison rule out half the book without inspecting it.

That’s binary search. The “dictionary” can be a sorted array, a range of integers [1, 10⁹], a real-valued interval, or even a stream of commits in git log — anything where a single yes/no probe at the midpoint cleaves the remaining search space cleanly in two.

The problem it solves

You have a sorted array nums and a target t. The brute force is a linear scan:

def find(nums: list[int], t: int) -> int:
    for i, x in enumerate(nums):
        if x == t:
            return i
    return -1

O(n) time, O(1) space. At n = 10⁶ that’s a million comparisons per query; at n = 10⁹ (think a sorted index file on disk) it’s already unusable, and you’re not even using the fact that the data is sorted.

Binary search uses the order. Probe the middle: if nums[mid] == t you’re done; if nums[mid] < t the answer must be to the right, so discard [0, mid]; otherwise discard [mid, n). Each probe halves what’s left, so the work is log₂(n) — about 20 probes for a million entries, 30 for a billion, 60 for the entire 64-bit integer range. That’s the win, and it’s why every database index, sorted file format, and “smallest X such that…” optimization eventually leans on it.

When to reach for it

Signals it’s binary search:

• Input is sorted, or you have a monotone predicate f(x) that is false-then-true (or true-then-false) over the search space.
• The naive solution scans linearly and is O(n) or worse, and the input or answer space is huge (10^9, 10^18) so log factors actually matter.
• The problem says “smallest / largest X such that…” and there’s a clear yes/no test for a given X.
• You need an insertion index, not just a hit/miss — that’s lower_bound / upper_bound.

Signals it’s not binary search: the data isn’t sorted and can’t be, the predicate isn’t monotone (some x work, then some don’t, then some do again), or the per-step check is more expensive than just scanning.

Flavor 1 — vanilla binary search

Closed interval [left, right]. Both endpoints are valid candidates; the loop runs while the interval is non-empty.

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2  # avoid overflow in C++/Java
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Worked example. nums = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19], target = 13.

Four probes for ten elements; for a billion entries it would be 30. The mid + 1 and mid - 1 updates are what guarantee progress: mid was already tested, so we exclude it from the next interval.

Flavor 2 — lower_bound / upper_bound

lower_bound(nums, t) returns the smallest index i with nums[i] >= t. upper_bound(nums, t) returns the smallest index i with nums[i] > t. The difference is one comparison, but it changes the off-by-one entirely.

The template uses a half-open interval [left, right) and while left < right:

def lower_bound(nums: list[int], t: int) -> int:
    left, right = 0, len(nums)        # right is one past the end
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < t:             # strict <  → lower_bound
            left = mid + 1
        else:
            right = mid               # NOT mid - 1; mid is still a candidate
    return left

def upper_bound(nums: list[int], t: int) -> int:
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= t:            # <=        → upper_bound
            left = mid + 1
        else:
            right = mid
    return left

Worked example. nums = [1, 2, 4, 4, 4, 6, 8], t = 4.

lower_bound:

Returns 2 — the first index of a 4.

upper_bound:

Returns 5 — one past the last 4. Count of 4s = 5 - 2 = 3. That subtraction is why these primitives exist: range counts in O(log n).

The critical move: right = mid (not mid - 1). With a half-open interval, mid itself might be the answer, so we keep it as the new upper bound. Pair that with while left < right and left = mid + 1 to guarantee the interval shrinks every step.

Flavor 3 — search on answer (Koko Eating Bananas, LC 875)

Koko has piles of bananas and h hours. At eating speed k bananas/hour, each pile takes ceil(pile / k) hours. Find the minimum k such that she finishes within h hours.

The feasibility check is monotone: if speed k works, every k' > k also works. So binary search over k ∈ [1, max(piles)].

import math

def min_eating_speed(piles: list[int], h: int) -> int:
    def hours_at(k: int) -> int:
        return sum(math.ceil(p / k) for p in piles)

    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        if hours_at(mid) <= h:
            right = mid          # mid works; maybe smaller works too
        else:
            left = mid + 1       # mid too slow
    return left

Worked example. piles = [3, 6, 7, 11], h = 8. Search space [1, 11].

Loop exits with left == right == 4. Answer: k = 4 bananas/hour. Each hours_at call is O(n); total work is O(n log(max(piles))). For piles of size 10^9 and n = 10^4, that’s about 3×10^5 ops — trivial.

The shape repeats for every “minimum X such that we still fit” or “maximum throughput we can sustain” problem: split-array-largest-sum, capacity-to-ship-packages, allocate-books, aggressive-cows. Write feasible(x), plug in the same scaffold.

Why it works — the invariant

The contract every step preserves: if the answer exists, it lives in [left, right] (or [left, right) for half-open). Each iteration inspects mid and rules out exactly half the interval based on the comparison; the other half — including the boundary that might still be the answer — stays.

This is why lower_bound writes right = mid instead of right = mid - 1. When nums[mid] ≥ t, mid itself is a valid candidate for the smallest qualifying index — discarding it would violate the invariant. The interval still strictly shrinks because left < right and mid = (left + right) // 2 rounds toward left, so right = mid always reduces the size by at least one. Vanilla search can use mid - 1 only because it returns immediately on equality, so mid is never a “still possibly the answer” candidate.

Monotonic feasibility is the prerequisite for search-on-answer. The predicate feasible(x) must be monotone in x — once it flips from false to true (or true to false), it must stay there. If feasibility is true at x = 5, false at x = 6, true again at x = 7, binary search will return garbage. Always sanity-check monotonicity before reaching for the template: “if x works, does every x' > x also work?” If yes, you have a binary search. If no, you have a different problem.

Complexity & memory tradeoffs

The O(log n) → O(1) memory cost in the iterative form is what makes binary search viable inside hot paths — database B-tree page searches, kernel schedulers, JIT lookups — where allocating a recursion frame per probe would be unacceptable.

Common pitfalls

• Integer overflow on mid. (left + right) // 2 is fine in Python, but in C++/Java it overflows when both are near INT_MAX. Always write left + (right - left) // 2 so the habit transfers.
• Infinite loop from the wrong update. Using while left < right with left = mid (instead of mid + 1) hangs forever when left + 1 == right because mid rounds down to left and never moves. Pair while left <= right with mid ± 1 updates, or while left < right with left = mid + 1 and right = mid. Don’t mix.
• Picking the wrong half on equality. For lower_bound the condition is nums[mid] < t (strict). For upper_bound it’s nums[mid] <= t. One character difference, totally different return value. Memorize the pair.
• Off-by-one on the answer range in search-on-answer. For Koko, left = 1 (speed 0 is meaningless). For “minimum capacity to ship”, left = max(weights) (you need at least one package to fit). Setting left = 0 is the most common bug — feasibility breaks at x = 0 and the loop returns garbage.
• Real-valued search spaces. For continuous answers (float), left = mid + 1 doesn’t make sense. Switch to a fixed iteration count (e.g., 100 rounds of mid = (l + r) / 2) or a tolerance check while r - l > 1e-9. Integer termination logic does not transfer.

Where you see this in production

• Python’s bisect module. bisect_left and bisect_right are literally lower_bound / upper_bound. CPython uses them in heapq, in statistics.median, and in any “keep a sorted list” code.
• Postgres B-tree index lookups. Each B-tree node holds keys in sorted order; locating a key inside a page is a binary search (_bt_binsrch in nbtsearch.c). Every indexed WHERE id = ? query hits this code path.
• git bisect. Given a known-good and known-bad commit, Git binary searches the commit graph (a linearisation of it) to find the bug-introducing commit. The “feasibility check” is whatever test you wrote — git bisect run ./test.sh automates it. Same template as Koko.
• Kafka offset lookup by timestamp. Log.fetchOffsetByTimestamp does a binary search across the segment index to map a timestamp to a byte offset, so consumers can seek to “messages after 9am” without a full scan.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.
• Errichto — Binary Search on Answer — www.youtube.com