Binary Search (Beyond the Sorted Array)

The bug you've definitely written

Here's the code most people write from memory:

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

There are two bugs, and they conspire. while lo < hi exits before checking the last candidate, so a single-element array returns -1 even when the element matches. Bug 2 is hi = mid instead of hi = mid - 1. On its own it doesn't hang this loop — when lo and hi are adjacent, mid computes to lo, hi drops to lo, and lo < hi goes false — but it means mid is never ruled out. Now watch what happens when you spot bug 1 and apply the obvious fix, changing the condition to lo <= hi: once lo == hi, mid == lo == hi, hi = mid changes nothing, and the loop runs forever. Patching one bug without the other trades a wrong answer for a hang.

These aren't obscure edge cases. They will eat your contest submission or your onsite if you're not careful.

The template you can trust

Pick one formulation and commit to it. Here's the one that works:

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1   # closed interval: both endpoints are valid candidates

    while lo <= hi:              # loop until the interval is empty
        mid = lo + (hi - lo) // 2   # avoids integer overflow (matters in C/Java)

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1        # mid is ruled out; search [mid+1, hi]
        else:
            hi = mid - 1        # mid is ruled out; search [lo, mid-1]

    return -1  # target not present

The invariant: at every point in the loop, if the target exists, it's somewhere in [lo, hi]. When we find arr[mid] < target, the target can't be at mid or anywhere left of it, so lo = mid + 1 preserves the invariant. Same logic for the other branch. When lo > hi, the interval is empty — the target isn't there.

The mid = lo + (hi - lo) // 2 instead of (lo + hi) // 2 matters in languages with fixed-size integers. In Python integers don't overflow so it's style, but write it the safe way anyway — the habit saves you in Java or C++.

Trace it on [1, 3, 5, 7, 9, 11, 14, 18, 22] with a target that isn't there — 8:

lo=0 hi=8  mid=4  arr[4]=9 > 8  → hi=3
lo=0 hi=3  mid=1  arr[1]=3 < 8  → lo=2
lo=2 hi=3  mid=2  arr[2]=5 < 8  → lo=3
lo=3 hi=3  mid=3  arr[3]=7 < 8  → lo=4
lo=4 > hi=3 — interval empty, return -1

The interval shrinks 9 → 4 → 2 → 1 → empty, and the miss falls out of the invariant with no special-casing. That's log base 2 of 9 ≈ 3.2, so 4 comparisons in the worst case. For 1 million elements, you need at most 20.

Find first / find last: same loop, different boundary

Sorted arrays with duplicates: [1, 2, 4, 4, 4, 6, 7]. You want the index of the first 4 (should be 2) or the last 4 (should be 4). The naive idea — find any occurrence, then walk left or right — degrades to O(n) on all-equal arrays.

The binary search version keeps the same skeleton. When you hit a match, instead of returning, you record the candidate and keep narrowing:

def find_first(arr, target):
    lo, hi = 0, len(arr) - 1
    result = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid        # record it, but keep going left
            hi = mid - 1
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

def find_last(arr, target):
    lo, hi = 0, len(arr) - 1
    result = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid        # record it, but keep going right
            lo = mid + 1
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

Both are O(log n). The match condition becomes "continue, but remember where you are" rather than "stop." This same idea — don't stop at the first match, keep pushing the boundary in one direction — reappears in every binary search variant.

In production code, don't hand-roll any of this. Python's bisect_left is find_first's boundary — it returns the insertion point, so check arr[i] == target afterward — and bisect_right gives you one past the last occurrence. C++ has lower_bound/upper_bound; Java has Arrays.binarySearch (which returns some matching index, not the first). Since Python 3.10, bisect_left also takes a key=, which covers most first-true searches over data you already hold in a list. Write the loop yourself in exactly two situations: interviews, and search-on-the-answer, where the predicate isn't membership in an array you can hand to a library.

Rotated sorted array

This one shows up constantly. Take a sorted array like [1, 3, 5, 7, 9, 11, 14] and rotate it at some pivot: [7, 9, 11, 14, 1, 3, 5]. The array isn't globally sorted anymore, but it has a key property: one of the two halves (split at mid) is always sorted.

flowchart LR
    A["[7, 9, 11, 14, 1, 3, 5]"] --> B{"arr[mid]=14\narr[lo]=7\narr[hi]=5"}
    B -- "arr[lo] ≤ arr[mid]\n→ left half sorted" --> C["Target in [7,14]?\nSearch left\nElse search right"]
    B -- "arr[mid] < arr[lo]\n→ right half sorted" --> D["Target in [mid,hi]?\nSearch right\nElse search left"]
    style A fill:#7c5cff,color:#0a0a0f
    style C fill:#22d3ee,color:#0a0a0f
    style D fill:#00ff9d,color:#0a0a0f

The insight: if arr[lo] <= arr[mid], the left half [lo..mid] is cleanly sorted. You can check in O(1) whether the target falls in that range — if yes, search there; if no, search the right half. Otherwise, the right half [mid..hi] is sorted, and you do the same check.

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

        if arr[lo] <= arr[mid]:          # left half is sorted
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1            # target is in the sorted left half
            else:
                lo = mid + 1            # target must be in the right half
        else:                            # right half is sorted
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1            # target is in the sorted right half
            else:
                hi = mid - 1            # target must be in the left half

    return -1

Still O(log n) — with one caveat: the half-is-sorted argument assumes distinct elements. With duplicates, say [1, 1, 1, 1, 0, 1, 1], arr[lo] <= arr[mid] no longer proves the left half is sorted, because both boundaries can equal arr[mid]. The standard patch: when arr[lo] == arr[mid] == arr[hi], you can't classify either half, so shrink with lo += 1; hi -= 1 and continue. That preserves correctness, but an all-equal array with one different value hidden somewhere forces you to shrink one step at a time — worst case O(n), and no algorithm does better on that input. The half-is-sorted observation is the key — without it you can't safely discard anything.

The real skill: binary search on the answer

This is where binary search goes from "I know the algorithm" to "I can use it to demolish hard problems."

The setup: you have a problem that asks for the minimum (or maximum) value X such that some condition holds. If that condition is monotonic — once it's true for some X, it's true for all larger X (or all smaller) — you can binary search over the range of possible X values.

The pattern:

def solve():
    lo, hi = lower_bound, upper_bound   # range of possible answers

    while lo < hi:                       # find the first value that satisfies
        mid = lo + (hi - lo) // 2
        if feasible(mid):                # check if mid is a valid answer
            hi = mid                    # mid works, but maybe something smaller does too
        else:
            lo = mid + 1               # mid doesn't work, need something larger

    return lo  # lo == hi: the smallest feasible value

Notice while lo < hi here — we want lo == hi at the end (both point to the answer), not an empty interval. And hi = mid (not mid - 1) because mid itself might be the answer.

Worked example: Koko eats bananas

Koko has n piles of bananas, h hours to eat them all. She eats at speed k bananas per hour (one pile at a time, and she waits if she finishes a pile early). What's the minimum k?

The monotonic structure: if speed k works (she finishes in <= h hours), any speed > k also works. We want the smallest k that works.

def min_eating_speed(piles, h):
    import math

    def feasible(speed):
        # how many hours does this speed take?
        return sum(math.ceil(p / speed) for p in piles) <= h

    lo, hi = 1, max(piles)   # speed 1 to max pile size (eating a pile per hour)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid           # mid works, look for something smaller
        else:
            lo = mid + 1       # mid is too slow
    return lo

The feasibility check is O(n). The binary search runs O(log(max(piles))) times. Total: O(n log m) where m is the max pile size. Without binary search on the answer, brute-forcing every possible speed from 1 to m would be O(n·m) — with piles of 10^9 bananas, that's not happening.

What "monotonic" looks like in the wild

The predicate feasible(mid) doesn't have to be obvious at first glance. Ask yourself: if I increase the candidate value by 1, does it become strictly easier or strictly harder to satisfy the constraint? If yes in one direction, you have a monotonic predicate.

Some examples you'll see in interviews:

Problem	Candidate X	Predicate
Ship packages in D days (LeetCode 1011)	Ship capacity	Can we ship all packages in D days at capacity X?
Split array into k parts with min max-sum	Subarray max sum	Can we split into k parts where each part's sum ≤ X?
Find peak element	—	Different structure; use lo/hi but on a derivative condition
Kth smallest in sorted matrix	Matrix value	How many elements ≤ X? Is it ≥ k?

The template is the same every time. What changes is what lo, hi, and feasible mean.

Complexity

Binary search's power is exactly what it sounds like:

Variant	Time	Space
Classic search (sorted array)	O(log n)	O(1)
Find first / find last	O(log n)	O(1)
Rotated sorted array	O(log n) distinct, O(n) with duplicates	O(1)
Binary search on answer	O(log(range) × f(n))	O(1) + whatever f(n) uses

The O(1) space is often undersold. Most O(log n) solutions you see use recursion — which brings O(log n) stack frames. The iterative version above is flat, using just lo, hi, and mid.

Common mistakes

Forgetting that mid can equal lo. With round-down division, lo = 4 and hi = 5 gives mid = 4 = lo. If you then set lo = mid in a "target is larger" branch, nothing changes — same lo, same hi, same mid next iteration — and you loop forever. The closed-interval template avoids this because it always steps past mid: lo = mid + 1 or hi = mid - 1.

Using while lo < hi when you want to check the found element. The lo < hi loop terminates with lo == hi — you still have to check arr[lo] after the loop. The lo <= hi template checks mid inside the loop every time, so you never need a post-loop check.

Binary searching on a non-monotonic predicate. "Find the element closest to the median" is not monotonic in the way that lets you binary search directly. If your predicate can flip from false→true→false as X increases, binary search will give you garbage. Confirm monotonicity before reaching for the pattern.

Integer division in the wrong place. mid = (lo + hi) // 2 always rounds down. That's usually fine, but in the "search for last occurrence" or "find upper bound" variants, you sometimes want mid = lo + (hi - lo + 1) // 2 (round up) to avoid the same infinite-loop issue where mid == lo when the interval has two elements and you set lo = mid. If you ever write lo = mid (not lo = mid + 1), round up.

Putting it all together

Binary search is O(log n) not because it's magic, but because it has one job: shrink the search space by half at each step. Everything else — the closed interval, the mid ± 1, the monotonic predicate — is in service of guaranteeing that the halving is always valid.

When you see a problem, the tell for binary search isn't "is there a sorted array?" — it's "can I define a space of candidates and a check that tells me, in one shot, whether to go left or right?" If yes, you have an O(log n) solution hiding in what might look like a brute-force problem.

For more on how search fits into the broader picture, see the searching crash course. The sorted array structure that makes all of this work is covered in arrays. And if you want the tree-based alternative that also gives you O(log n) search (with dynamic insertions), see binary search trees.