Binary Search: Halving a Sorted World Down to One Answer

"I’m thinking of a number between 1 and 100 — guess it." You say 50. "Higher." You say 75. "Lower." You say 62... and within about seven guesses you’ve pinned it, every single time, no matter which number they picked. That’s not luck. You’ve stumbled onto a strategy so good it feels like cheating: every guess throws away half of what’s left.

That strategy has a name — binary search — and it’s one of the highest-return ideas in all of programming. It turns a search through a billion things into thirty guesses. By the end of this article you and I will have built it together, nailed the three details that trip up almost everyone, and then gone somewhere most tutorials never take you: searching for an answer that isn’t even in an array.

Let’s start nowhere near a computer

Forget numbers for a second. Picture a fat paper dictionary, and I ask you to find the word serendipity.

You don’t start on page one. You flop the book open somewhere near the middle, and your two thumbs come to rest on the left and right edges of the pages still in play. Say you land on M. Serendipity starts with S, which comes after M, so — and here’s the whole trick — every page to the left of your thumb no longer exists for you. You slide your left thumb up to meet the middle and flop open the middle of what remains. Now you’re in T. Too far. Your right thumb jumps inward. Middle again: R. And so on, each flop cutting the surviving pages roughly in half, until a single page is left and your word is on it.

Watch what your two thumbs are really doing. They mark a shrinking window — call the left one lo and the right one hi — and they hold a promise between them:

If the word is anywhere in this dictionary, it is between my two thumbs.

That promise is the beating heart of binary search. It’s called the invariant, and it’s true at the start (the word, if present, is somewhere in the whole book) and stays true after every single flop (you only ever move a thumb past pages you’ve proven can’t hold the word). When your thumbs finally squeeze together, the invariant leaves exactly one possibility standing.

So the entire method is three moves, repeated:

• Look at the middle of the surviving window.
• Compare it to what you want.
• Move one thumb to kill the half that can’t contain the answer.

Every hard detail later in this article is just about doing those three moves without lying to the invariant.

Where you already meet it

Once you know the shape — "sorted, so halve it" — you spot it everywhere. Your database answers WHERE id = 91823 in microseconds because its index is a sorted structure it binary-searches instead of scanning every row. The standard library ships it as Arrays.binarySearch and Collections.binarySearch. Even finding a contact by dragging the little A–Z rail on your phone is a coarse binary search you’re doing with your thumb.

But the most illuminating cousin hunts through something that isn’t a list of values at all — it’s a list of versions of your code. When a bug sneaks into a project with ten thousand commits, git bisect finds the exact commit that introduced it without you reading a single diff. You tell git one commit that was good and one that’s bad, and it checks out the commit halfway between them and asks you: is the bug here? Your one-word answer — "good" or "bad" — throws away half the history, and about fourteen questions later git names the culprit out of ten thousand.

Look closely at why that works, because it’s the seed of the deepest idea in this article. The commits aren’t sorted by value — there’s no "bigger" or "smaller" commit. They’re sorted by a yes/no property that flips exactly once: every commit before the bug is good, every commit from the bug onward is bad. good good good | bad bad bad. That single flip is all binary search actually needs. Hold that thought — we’re going to build a whole class of problems on it.

What it actually looks like

Here’s a sorted array, and we’re hunting for 72. The two thumbs are lo and hi; mid is the cell halfway between them.

We compute mid = 5 and read a[5] = 23. It’s below 72, so 72 — if it’s here at all — must live to the right of mid. In one comparison we delete indices 0 through 5. The window that survives is a[6..10], and we repeat the exact same move on it.

That "delete half per comparison" is where the speed comes from. Starting at 100 items you’re down to 50, then 25, 13, 7, 4, 2, 1 — about seven steps. A billion items falls in thirty. Formally the work is O(log n): the number of halvings it takes to shrink n to 1. Compared to a linear scan’s O(n), that’s not a small win, it’s a different universe — log₂(1,000,000,000) is under 30.

Let’s build one, step by step

We’ll assemble the full class at the end. For now, one piece at a time.

Step 1 — set up the window and the invariant

Two thumbs, so two variables. lo starts at the first index, hi at the last. The invariant we’re protecting: if target is in the array, it’s in a[lo..hi] — and right now that window is the whole array, so it’s trivially true.

int lo = 0, hi = a.length - 1;   // target, if present, lives in a[lo..hi]

That hi = a.length - 1 matters: the window is inclusive on both ends. a[hi] is a real, searchable cell, not one-past-the-end. (Some people prefer a half-open window; we’ll meet that variant when we do lower bound, and I’ll show you why it’s cleaner there.)

Step 2 — look at the middle, kill a half

Compute mid, read a[mid], and branch three ways. Equal? Done. Too small? The answer can’t be at mid or anywhere left of it, so slide lo up. Too big? Slide hi down. Each branch moves a thumb past mid, so the window strictly shrinks — which is exactly what keeps the invariant honest and guarantees we terminate.

Follow the three rows: the light window halves each iteration until mid finally lands on 72 and we return its index. In code:

while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == target) {
        return mid;                 // found it
    } else if (a[mid] < target) {
        lo = mid + 1;               // drop the left half, mid included
    } else {
        hi = mid - 1;               // drop the right half, mid included
    }
}
return -1;                          // window emptied — target isn't here

The rule to burn in: mid + 1 and mid - 1, never plain mid. We already compared a[mid] — it’s not equal, so it can’t be the answer, so we exclude it. Write lo = mid instead of lo = mid + 1 and the day lo == mid arrives, the window stops shrinking and you spin forever. The excluded mid is what makes progress.

Step 3 — the overflow trap that ships to production

Look again at mid = lo + (hi - lo) / 2. The "obvious" way to write the midpoint is (lo + hi) / 2, and it’s correct — right up until lo + hi is bigger than the largest int. On a huge array, both indices can sit near two billion, their sum wraps past INT_MAX into a negative number, and mid becomes a negative index that stabs off the front of the array.

This isn’t a hypothetical. It’s one of the most famous bugs in the field: binary search sat broken inside the standard library and in Programming Pearls for two decades before someone hit an array big enough to trip it. The fix costs nothing — compute the offset from lo instead of summing the endpoints:

int mid = lo + (hi - lo) / 2;   // (hi - lo) can't overflow; adding to lo stays in range

hi - lo is the window’s width, always a valid non-negative int; halving it and adding to lo can never leave the array. Same answer, zero overflow. Write it this way every time and never think about it again.

Step 4 — <= or <? The off-by-one that returns wrong answers

The other detail that separates a working binary search from a subtly broken one is the loop condition. Ours says while (lo <= hi). Why not lo < hi?

Because our window is inclusive — a[hi] is a candidate we still have to check. When the window narrows to a single cell, lo == hi, and that cell might be the answer. With <=, the loop runs one more time and checks it. With <, the loop exits early and skips it.

Here’s the bug made concrete. Search the one-element array [5] for 5. We start lo = 0, hi = 0.

• With while (lo <= hi): the loop runs, mid = 0, a[0] == 5, we return 0. Correct.
• With while (lo < hi): 0 < 0 is false, the loop never runs, we return -1. The array literally contains 5 and we said it doesn’t.

The condition has to match the window. Inclusive hi pairs with <=; a half-open hi (one past the end) pairs with <. Mixing them is the single most common way to get a binary search that’s right on most inputs and wrong on the edges — which is the worst kind of wrong, because your tests probably miss it.

Leftmost and rightmost: lower bound and upper bound

Plain search has a blind spot: with duplicates, it returns some matching index, but which one? If the array is [2, 4, 4, 4, 4, 7, 9] and you search for 4, you might get index 1, 2, 3, or 4 depending on how the halving falls. Often you need the first 4, or the position just past the last 4, or the count of 4s. That’s what lower bound and upper bound give you.

• lower bound — the first index i where a[i] >= target. For 4, that’s index 2 (the first 4).
• upper bound — the first index i where a[i] > target. For 4, that’s index 6 (just past the last 4).

They bracket the whole run of equal values, and the gap between them is the count: upper - lower = 6 - 2 = 4, exactly the number of 4s. And because lower is defined as "first index not below the target," it’s also the correct insertion point — where you’d slot a new value to keep the array sorted, whether or not it’s already present.

Both use the half-open window I hinted at earlier: hi starts at a.length (one past the end), the loop is while (lo < hi), and — crucially — the "keep this candidate" branch does hi = mid rather than hi = mid - 1, because mid itself might be the answer we’re looking for.

public static int lowerBound(int[] a, int target) {
    int lo = 0, hi = a.length;          // half-open window [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) {
            lo = mid + 1;               // mid too small: answer is strictly right
        } else {
            hi = mid;                   // a[mid] >= target: mid might BE the answer
        }
    }
    return lo;                          // first index not below target (may be a.length)
}

Upper bound is the same code with a single character changed: a[mid] <= target instead of a[mid] < target, which pushes the boundary past equal values too. Notice this version has no == target branch at all — it never stops early on a match, because "find the boundary" is a different question from "find any hit." That difference is the bridge to the most powerful use of binary search there is.

The real unlock: binary search on the answer

Here’s the leap that turns binary search from a lookup trick into a problem-solving superpower — and it’s the one facet worth slowing all the way down for.

Go back to git bisect. It didn’t search sorted values; it searched a yes/no property that flips exactly once: good good good | bad bad bad. Lower bound does the same thing — it’s really hunting the flip point of "is a[mid] >= target?", which goes false false | true true across a sorted array. Strip away the array entirely and you’re left with the pure idea:

If you have a monotonic predicate — a true/false test that, once it turns true, stays true — you can binary-search for the exact point where it flips, even when there’s no array to search at all.

The candidates on that axis don’t have to be array indices. They can be possible answers to your actual problem — capacities, speeds, time limits, budgets. You define a predicate feasible(x) that asks "does answer x work?", check that it’s monotonic (bigger x is always at least as easy, so once feasible it stays feasible), and binary-search for the smallest x where feasible first becomes true. That smallest feasible answer is your result. This is called binary search on the answer, and it unlocks a huge family of "minimize the maximum" and "smallest value that still works" problems that look nothing like search.

Let’s make it concrete with a classic. You have to ship a list of packages in their given order off a conveyor belt, and you get to pick the capacity of the boat. With more capacity you finish in fewer days; with less, more days. Question: what’s the smallest capacity that still gets everything shipped within D days?

Read that table top to bottom: as capacity climbs, the days needed only ever fall — never rise. That’s the monotonicity we need. So "can we finish within 5 days?" is a predicate that’s false for small capacities and true for big ones, flipping exactly once — and we binary-search for the flip.

The search space isn’t an array; it’s the range of possible capacities. The smallest capacity worth considering is the heaviest single package (a boat that can’t lift the biggest box is hopeless). The largest worth considering is the sum of everything (carry it all in one day). We binary-search that numeric range:

public static int shipWithinDays(int[] weights, int days) {
    int lo = 0, hi = 0;                 // the ANSWER space: possible capacities
    for (int w : weights) {
        lo = Math.max(lo, w);           // must at least hold the heaviest box
        hi += w;                        // could carry the whole cargo in one day
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canShip(weights, days, mid)) {
            hi = mid;                   // feasible: try a smaller capacity
        } else {
            lo = mid + 1;               // infeasible: we need more
        }
    }
    return lo;                          // smallest capacity that fits `days` days
}

The predicate is a plain linear pass — greedily pack the belt until the current day is full, then start a new day, and count how many days it took:

private static boolean canShip(int[] weights, int days, int capacity) {
    int needed = 1, load = 0;
    for (int w : weights) {
        if (load + w > capacity) {
            needed++;                   // this box overflows today — roll to tomorrow
            load = 0;
        }
        load += w;
    }
    return needed <= days;
}

Stare at the loop skeleton and you’ll see it’s identical to lower bound: while (lo < hi), feasible does hi = mid, infeasible does lo = mid + 1, and we return lo — the smallest feasible answer. The only thing that changed is what feasible means. Instead of "is this array cell big enough," it’s "can a boat this size finish in time." That’s the whole art: spot the monotonic predicate hiding in the problem, and binary-search its flip point. Once you can do that, a startling number of "find the minimum X such that Y is possible" problems collapse into fifteen lines.

The single thing you must double-check before using it: is the predicate actually monotonic? If feasible(x) can flip from true back to false as x grows, there’s no single boundary to find and binary search will happily return nonsense. Prove the monotonicity — "more capacity can never need more days" — and only then trust the halving.

Binary search vs. scanning the list

The alternative is the honest linear scan: walk every element until you find the target. It’s simpler and it needs no sorting — so when does binary search earn its keep? Let n be the number of elements.

The trade-off is upfront cost versus per-query cost. Sorting is O(n log n) paid once; after that every lookup is O(log n) forever. So if you search a dataset once, a linear scan wins — sorting first would be wasted work. Search it thousands of times, and the one-time sort is a rounding error against thousands of near-instant lookups. And binary search on the answer plays in a league of its own: it replaces "try every possible answer" (O(range)) with O(log(range)) calls to a feasibility check, which is what makes otherwise-intractable ranges — capacities up to billions — finish in a blink.

The complete implementation

Everything above, assembled — classic search, both bounds, the answer-space search, and integer square root as a bonus flip-point hunt:

package dev.fiveyear.search;
 
public final class BinarySearch {
 
    private BinarySearch() {}
 
    /** An index of target in the sorted array, or -1 if absent. O(log n). */
    public static int search(int[] a, int target) {
        int lo = 0, hi = a.length - 1;      // target, if present, is in a[lo..hi]
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;   // avoid (lo + hi) overflow
            if (a[mid] == target) {
                return mid;
            } else if (a[mid] < target) {
                lo = mid + 1;               // drop the left half, mid included
            } else {
                hi = mid - 1;               // drop the right half, mid included
            }
        }
        return -1;                          // lo > hi: the window is empty
    }
 
    /** First index i where a[i] >= target (the insertion point). In [0, a.length]. */
    public static int lowerBound(int[] a, int target) {
        int lo = 0, hi = a.length;          // half-open window [lo, hi)
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] < target) {
                lo = mid + 1;               // mid too small: boundary is to the right
            } else {
                hi = mid;                   // a[mid] >= target: mid might be the answer
            }
        }
        return lo;
    }
 
    /** First index i where a[i] > target. In [0, a.length]. */
    public static int upperBound(int[] a, int target) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] <= target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
 
    /** Whether target is present, via lower bound. */
    public static boolean contains(int[] a, int target) {
        int i = lowerBound(a, target);
        return i < a.length && a[i] == target;
    }
 
    /** How many times target occurs. */
    public static int countOf(int[] a, int target) {
        return upperBound(a, target) - lowerBound(a, target);
    }
 
    /** Smallest ship capacity to move weights in order within `days` days. */
    public static int shipWithinDays(int[] weights, int days) {
        int lo = 0, hi = 0;                 // search the answer space, not an index
        for (int w : weights) {
            lo = Math.max(lo, w);           // capacity must hold the heaviest box
            hi += w;                        // whole cargo in a single day
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (canShip(weights, days, mid)) {
                hi = mid;                   // feasible: try smaller
            } else {
                lo = mid + 1;               // infeasible: need more
            }
        }
        return lo;
    }
 
    /** The monotonic predicate: can this capacity finish within `days` days? */
    private static boolean canShip(int[] weights, int days, int capacity) {
        int needed = 1, load = 0;
        for (int w : weights) {
            if (load + w > capacity) {
                needed++;                   // start a new day
                load = 0;
            }
            load += w;
        }
        return needed <= days;
    }
 
    /** Floor of the square root of n (n >= 0): the largest r with r*r <= n. */
    public static int isqrt(int n) {
        long lo = 0, hi = (long) n + 1;     // find the smallest r with r*r > n...
        while (lo < hi) {
            long mid = lo + (hi - lo) / 2;
            if (mid * mid > n) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return (int) (lo - 1);              // ...then step back one
    }
}

And here it is producing exactly the outputs the comments claim:

int[] a = {1, 3, 5, 7, 9, 11};
BinarySearch.search(a, 7);              // 3
BinarySearch.search(a, 8);              // -1  — absent, falls between cells
BinarySearch.search(new int[] {}, 5);  // -1  — empty array
 
int[] d = {2, 4, 4, 4, 4, 7, 9};
BinarySearch.lowerBound(d, 4);         // 1   — first 4
BinarySearch.upperBound(d, 4);         // 5   — just past the last 4
BinarySearch.countOf(d, 4);            // 4   — four copies
BinarySearch.lowerBound(d, 5);         // 5   — insertion point for a missing value
BinarySearch.contains(d, 5);           // false
 
int[] w = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
BinarySearch.shipWithinDays(w, 5);     // 15  — smallest capacity fitting 5 days
BinarySearch.shipWithinDays(w, 1);     // 55  — one day: carry it all
 
BinarySearch.isqrt(8);                 // 2   — floor
BinarySearch.isqrt(2147483647);        // 46340 — Integer.MAX_VALUE, no overflow

The interview corner

Binary search shows up constantly precisely because it’s small enough to write on a whiteboard and deep enough to reveal whether you actually understand invariants. Here’s how to walk in ready.

Ask these before you write a line:

• "Is the input guaranteed sorted, and by the exact key I’m searching?" If not, binary search is off the table until you sort (O(n log n)), which may cost more than a single O(n) scan. Establish this first — it decides the whole approach.
• "Are there duplicates, and do you want any match, the first, or the last?" "Any" is plain search; "first/last/count" is lower/upper bound. Guessing wrong here writes the wrong algorithm.
• "How big can the indices or the answer range get?" Near INT_MAX and you’ll want the overflow-safe midpoint and possibly long bounds — say so out loud; it shows range awareness.

The follow-up ladder — where a strong candidate keeps climbing:

1. "The array is sorted but then rotated, like [6,7,8,1,2,3]." Still O(log n): at each mid, one half is guaranteed sorted — test whether the target lies within that sorted half, and recurse into the correct side.
2. "Find the peak of an array that rises then falls." No target to compare against, so compare a[mid] to a[mid+1]: you’re on an upslope or a downslope, and that alone tells you which half holds the peak. Binary search needs a direction, not a target.
3. "Search a matrix sorted row-wise and column-wise." Start at the top-right corner: too big → step left, too small → step down. It’s a staircase walk in O(m + n) — binary search’s cousin, where each comparison still eliminates a whole row or column.
4. "Minimize the largest sum when splitting an array into k contiguous parts." Binary-search the answer: the candidate is "largest allowed part-sum," the predicate "can we do it in ≤ k parts," monotonic in the candidate — the exact ship-capacity pattern in disguise.
5. "The data is 500 GB on disk, not in memory." The comparison model still holds, but random disk seeks are brutal, so a plain binary search’s log n seeks are slow; real systems use a B-tree, a fat, disk-friendly generalisation that binary-searches within each big block to slash the number of seeks. (This is why your database index is a B-tree — see how a trie makes the same "narrow the search space" move for strings.)

Three mistakes that fail the round:

• mid = (lo + hi) / 2. It’s correct until the indices are huge, then it overflows to a negative index and crashes. Always lo + (hi - lo) / 2.
• Mismatched window and condition. Inclusive hi with <, or half-open hi with <=, quietly skips or double-counts the boundary element. The condition must follow from the window, not from habit.
• lo = mid instead of lo = mid + 1 in an inclusive search. The moment lo == mid, the window stops shrinking and the loop spins forever. Every branch must exclude the mid you just compared, or prove the window still shrinks.

Where to go from here

You now own the core: a sorted world, two thumbs, and one question — which half can I throw away? — asked until one answer stands. Three natural next stops, each one loosening an assumption:

• Binary search trees and B-trees — bake the halving into the data structure itself, so inserts and deletes stay O(log n) too, not just lookups. The B-tree is what your database and filesystem actually run.
• Ternary search — when the function isn’t monotonic but unimodal (rises then falls), halving fails but "thirds" finds the peak. The same divide-and-discard spirit for optimisation.
• Deeper "search on the answer" problems — Koko eating bananas, splitting arrays, the smallest divisor, allocating pages: once you’ve seen the flip-point pattern, a whole genre of interview problems stops looking hard. Pair it with the graph-search intuition in Dijkstra’s algorithm and the merge-and-query speed of union-find and you’ve got the three algorithmic ideas that carry most interview rounds.

Next time you win "guess my number" in seven tries, you’ll know it wasn’t a lucky streak — it was O(log n), and you can now write it down without a single off-by-one.