Skip to main content
Sorting & Searching6 min read

Binary Search

Halve the search space every step, O(log n) on anything sorted.

Think of guessing a number between 1 and 1000 when every guess earns a reply of higher or lower. You would never guess 1, 2, 3, and so on. You would guess 500, then 250 or 750, halving the possibilities every time. Ten guesses suffice for a thousand numbers; twenty for a million. That is binary search.

The requirement is that the data is sorted, or more generally that it splits cleanly into a no region followed by a yes region. Given that, binary search finds your target in O(log n) time. The number of steps grows only with the number of times you can halve n. It is also famously easy to get subtly wrong, so this lesson gives you one template to trust and the pitfalls it protects you from.

The classic loop

Binary search maintains a shrinking window of candidate positions, tracked by two indices: lo, the lowest index still possible, and hi, the highest. Each round, compute the middle index mid and compare the element there to the target. A match ends the search. If the middle element is too small, the target can only live to the right, so discard the left half by setting lo to mid + 1. Too big, discard the right half with hi = mid - 1.

Every comparison eliminates half of the remaining window, which is the entire source of the speed: a million elements need at most about 20 comparisons, a billion about 30. The loop runs while lo <= hi; if the window empties without a match, the target is absent. Java gives you this as Arrays.binarySearch, but interviews expect you to write and adapt the loop yourself, because the interesting problems are variations on it.

Java
int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

The lo/hi/mid template, and why the details matter

Three lines of the template carry all the safety, and each guards a specific bug. First, mid = lo + (hi - lo) / 2 rather than (lo + hi) / 2: with very large arrays, lo + hi can exceed the maximum int value and overflow into a negative number. The subtraction form computes the same midpoint without that risk, a legendary bug that survived for years in published libraries.

Second, lo = mid + 1 and hi = mid - 1, never lo = mid or hi = mid in this closed-interval style. Because mid has already been examined and rejected, keeping it in the window wastes a step at best, and at worst (when the window is down to one or two elements) the window stops shrinking and the loop spins forever. Third, the condition lo <= hi, not lo < hi: with the closed interval, a one-element window has lo equal to hi, and using strict less-than would skip checking that final candidate. Fix these three details in your fingers as one non-negotiable template and an entire genus of off-by-one bugs disappears.

Finding boundaries, not just targets

The exact-match version is actually the least common form in real problems. More often you want a boundary: the first index whose value is at least the target, or the last index before values get too big. Picture the array as answering a yes/no question at each index. Say, is a[i] >= target? Sorted order guarantees the answers look like NNNNYYYY, and the goal is the first Y.

The variation is small but sacred: when mid answers yes, it might itself be the first yes, so you record it and continue searching left; when mid answers no, the boundary is strictly right of it. This lower-bound form handles duplicates gracefully (it finds the first occurrence of a repeated value), tells you where an absent element would be inserted, and is the version you will reuse constantly. Trace it on a two-element array by hand once. Watching lo and hi converge builds more trust than any explanation.

Java
int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length - 1, ans = a.length;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] >= target) {
            ans = mid;      // candidate; keep looking left
            hi = mid - 1;
        } else {
            lo = mid + 1;   // boundary must be right of mid
        }
    }
    return ans;
}

Searching the answer space

Here is the leap that turns binary search from a lookup trick into a problem-solving strategy: the thing you search does not have to be an array. Suppose you must ship packages within D days and want the smallest ship capacity that works. There is no array of capacities, but there is a monotonic pattern. A monotonic condition is one that flips exactly once: every capacity below some threshold fails, every capacity at or above it succeeds. NNNNYYYY again.

So binary search the range of possible answers. lo and hi become the smallest and largest conceivable capacities. For each mid, run a checker. Can we ship in D days with capacity mid?, usually a simple greedy simulation. If yes, try smaller; if no, go bigger. The total cost is the checker's cost times log of the answer range. This binary search on the answer pattern cracks problems about minimum speeds, maximum distances, and smallest feasible budgets, and it is one of the highest-value patterns in interviews. It also completes the story sorting began: order in, logarithms out. From here, the same divide-the-space instinct carries you into trees. Structures that are, at heart, binary search made physical.

key takeaways
Binary search halves the candidate window every comparison, giving O(log n) time on any sorted array.
Memorize the template exactly: mid = lo + (hi - lo) / 2, loop while lo <= hi, and always move to mid + 1 or mid - 1.
The mid formula with subtraction prevents integer overflow, and the strict window shrink prevents infinite loops.
The lower-bound variant finds the first index satisfying a condition, which handles duplicates and insertion points.
When a problem asks for the smallest or largest value passing a monotonic yes/no check, binary search the answer range itself.

Frequently asked

Why does binary search require sorted data?

The algorithm's whole logic is that one comparison tells you which half of the window to discard. That deduction is only valid if everything left of a position is smaller and everything right is larger. On unsorted data the comparison tells you nothing about the halves, so you could discard the half that actually contains the target.

How do I stop making off-by-one mistakes with lo, hi, and mid?

Pick one convention and never improvise. Use the closed-interval template: hi starts at length minus 1, the loop runs while lo <= hi, and updates are always mid + 1 or mid - 1. Then test your loop mentally on a one-element and a two-element array; nearly every off-by-one bug shows up in those two cases.

What does binary search on the answer mean if there is no array?

You treat the range of possible answers, like all capacities from 1 to some maximum, as the thing being searched. As long as a yes/no feasibility check flips exactly once across that range, you can binary search for the flip point. Each step runs the check at the midpoint value and keeps the half where the boundary must lie.