Binary Search

A bad deploy is hiding somewhere in the last 500 commits and production is on fire — do you re-test all 500, or do you find it in 9 checks? Binary search is the art of throwing away half the world at every step, and it’s deceptively easy to describe and famously easy to get wrong: a classic study found most professional implementations had a bug. This module gives you a template that doesn’t.

The Goal

• State the invariant that makes binary search correct — and use it to debug any variant
• Write the Java template from memory, including why lo + (hi - lo) / 2 and not (lo + hi) / 2
• Name the three classic bug families and spot them in broken code
• Implement first/last-occurrence search by controlling which way the boundary collapses
• Recognize when to binary search the answer space instead of an array
• Explain why O(log n) means a billion elements cost ~30 steps

The Lesson

The invariant — the one sentence that makes it correct

Binary search maintains a promise from the first line to the last:

If the answer exists, it is inside [lo, hi]. Always.

Every move you make must keep that promise true. You look at the middle; if the middle is too small, the answer can’t be at mid or anywhere left of it, so lo = mid + 1 keeps the promise. Too big → hi = mid - 1. When lo crosses hi, the range is empty — the promise says the answer was always inside it, so an empty range means not here.

Every binary search bug you will ever write is a move that silently breaks this promise — either kicking the answer out of the range, or failing to shrink the range at all. When a variant confuses you, stop tracing and ask: “what is my [lo, hi] promising right now?” That question debugs all of them.

The Java template — memorize this shape

static int binarySearch(int[] arr, int target) {
    int lo = 0;
    int hi = arr.length - 1;            // [lo, hi] is INCLUSIVE on both ends
    while (lo <= hi) {                  // <= because a 1-element range is still valid
        int mid = lo + (hi - lo) / 2;   // NOT (lo + hi) / 2 - see below
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;   // mid is ruled out - skip past it
        else hi = mid - 1;                     // mid is ruled out - skip past it
    }
    return -1;                          // range emptied - the promise says: not here
}

Why lo + (hi - lo) / 2? Because lo + hi is an int addition, and ints overflow. If lo and hi are both around 1.5 billion (a huge array, or a search over an answer space — coming below), lo + hi exceeds Integer.MAX_VALUE (~2.1 billion), wraps to a negative number, and your mid becomes garbage like -400_000_000. Array access explodes; answer-space search silently corrupts. hi - lo can never overflow because both fit in the range already. This exact bug sat in the JDK’s own Arrays.binarySearch for nine years before anyone noticed. Write the safe form every time, and say why in the interview — it’s free credit.

Trace it once by hand so the template stops being symbols. Searching for 23 in [4, 9, 12, 23, 38, 45, 57, 70] (indexes 0–7):

Too lucky. Search for 45 instead:

Now 40 (absent):

That final row is the promise doing its job: the range emptied, so 40 was never there. Do this trace yourself on paper for one present and one absent value — it’s ten minutes that makes the next ten problems easy.

The built-ins exist — know them, then write your own anyway. Java ships Arrays.binarySearch(arr, key) for arrays and Collections.binarySearch(list, key) for lists (both covered in the Collections module), and TreeMap is binary search living inside a data structure. In real code, use them. In interviews and in every variant below, you write it yourself — the built-ins can’t do first-occurrence, answer spaces, or rotated arrays, which is exactly where the questions live.

The three bug families

Every broken binary search is one of these. Learn them as families and you can debug any variant on sight:

The infinite loop deserves a closer look because it’s the one that bites in variants: with lo = 3, hi = 4, mid is 3. If your update is lo = mid instead of lo = mid + 1, then lo stays 3 — the range never shrinks, the loop never ends. Rule: every iteration must make the range strictly smaller. If mid has been examined and ruled out, step past it.

Variation 1 — first/last occurrence (boundary binary search)

[1, 3, 5, 5, 5, 5, 9] — where does the block of 5s start? Plain binary search returns some 5, whichever mid hits first. The fix: when you find a match, don’t stop — remember it and keep searching the half where an even better answer might live:

static int firstOccurrence(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    int found = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            found = mid;        // a candidate - but an earlier one may exist
            hi = mid - 1;       // keep hunting LEFT
        } else if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return found;
}

lastOccurrence is the same code with one flip: lo = mid + 1 on a match — hunt right instead. This is boundary binary search: you’re not finding “a match,” you’re finding the edge where the array flips from not-target to target. Count of occurrences = last − first + 1, in O(log n), no scanning. Most “harder” binary search interview questions are secretly this.

Variation 2 — search the ANSWER space (the Koko move)

The biggest mental upgrade in this module: the sorted thing you search doesn’t have to be an array.

Koko Eating Bananas, the canonical example: piles of bananas, h hours, Koko eats at speed k bananas/hour — find the minimum k that finishes in time. There’s no sorted array anywhere. But look at the answers: at speed 1, she’s too slow (fails). At speed 1,000,000, she trivially finishes (succeeds). And it’s monotonic — if speed k works, every speed above k works too:

speed:  1  2  3  4  5  6  7  8 ...
works?  no no no no YES YES YES YES

That’s a sorted boolean sequence — false, false, false, true, true, true — and you binary search for the first true:

static int minEatingSpeed(int[] piles, int h) {
    int lo = 1;
    int hi = 1_000_000_000;                 // any speed that certainly works
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canFinish(piles, mid, h)) {
            hi = mid;        // mid works - but maybe something smaller does too
        } else {
            lo = mid + 1;    // mid fails - the answer is strictly above
        }
    }
    return lo;               // lo == hi == the first speed that works
}

static boolean canFinish(int[] piles, int speed, int h) {
    long hours = 0;
    for (int p : piles) {
        hours += (p + speed - 1) / speed;   // ceiling of p divided by speed
    }
    return hours <= h;
}

Note the shape changed: hi = mid (not mid - 1) because a working mid is still a candidate answer — you can’t rule it out, only everything above it. And the loop is lo < hi so it can’t infinite-loop with hi = mid. The recognition trigger is golden: “minimize the maximum” or “maximize the minimum” or “smallest X such that condition holds” = binary search on the answer. Ship capacity, smallest divisor, minimum days — all this one move.

Variation 3 — rotated arrays, in brief

[6, 7, 1, 2, 3, 4, 5] — sorted, then rotated. The promise still holds with a twist: at any mid, one of the two halves is still perfectly sorted (compare arr[lo] with arr[mid] to know which). Check if the target sits inside the sorted half’s range; if yes, search there, otherwise search the messy half — which is itself a rotated sorted array. You still kill half per step: O(log n). That’s the whole idea; drill it in Problems below.

O(log n) — what it actually buys

Each step halves what’s left, so steps = “how many times can you halve n” = log₂ n. A billion sorted elements — every UPI transaction ID in India for months — and you find any one of them in 30 comparisons. Double the data, pay one more step. This is why “is the data sorted?” should fire in your head like an alarm in every problem: sorted means log n is on the table.

flowchart LR
    A["1 billion items"] --> B["500 million"]
    B --> C["250 million"]
    C --> D["..."]
    D --> E["1 item after about 30 halvings"]

See It Move

Watch how the dimmed-out half is never looked at again — that’s the entire trick.

Step through it and notice:

• mid is computed fresh each step and the eliminated half dims — the promise [lo, hi] is exactly the bright region.
• When the target is missing, watch lo and hi cross. That crossing IS the “not found” — no special check needed.
• Search for the first and last elements — these are exactly the inputs that expose off-by-one bugs in a broken template.
• Count the steps for the array size shown, then verify: it never exceeds log₂ n rounded up.

Spot The Pattern

Where It Runs In Real Life

git bisect — finding the bad deploy. Tests pass at commit 1, fail at commit 500. git bisect checks the middle commit: pass means the bug is in the newer half, fail means the older half. 500 commits → ~9 checkouts instead of 500. It’s binary search on a monotonic good-good-bad-bad timeline — literally the First Bad Version problem, and a skill you will use on a real on-call day.

Database B-tree index lookups. When module DSA 01 said an index turns a 50-million-row scan into a few page reads, this is the mechanism: a B-tree is a binary search tree widened so each node holds hundreds of sorted keys (one disk page). Finding a key is binary search within each node, descending 3–4 levels total. Every WHERE id = ? your future Spring Boot app runs rides this.

Autocomplete prefix ranges. Type “cri” into a search box backed by a sorted term list — the matches for the prefix form one contiguous block. First-occurrence binary search finds where “cri…” starts, a second boundary search finds where it ends, and everything between is the suggestion list. Two log-n searches, zero scanning, even with millions of terms.

Rate limiters and timestamp windows. “How many requests did this user make in the last 60 seconds?” with requests stored as a sorted timestamp list: binary search for now - 60 gives the cut point; everything after it counts. Sorted-by-time data is everywhere in backend work, and binary search is how you slice it cheaply.

Build This

You’re building the template, then the variant, then the answer-space move — and you’ll plant each bug family on purpose so you recognize it forever.

1. Create SearchLab.java:

import java.util.Arrays;
import java.util.Random;

public class SearchLab {

    public static void main(String[] args) {
        int n = 1_000_000;
        int[] arr = new int[n];
        Random rng = new Random(7);
        for (int i = 0; i < n; i++) arr[i] = rng.nextInt(10_000_000);
        Arrays.sort(arr);

        int target = arr[742_913];   // guaranteed present

        long t1 = System.nanoTime();
        int idxScan = linearScan(arr, target);
        long scanNanos = System.nanoTime() - t1;

        long t2 = System.nanoTime();
        int idxBin = binarySearch(arr, target);
        long binNanos = System.nanoTime() - t2;

        System.out.println("linear scan   -> index " + idxScan + " in " + scanNanos / 1_000 + " us");
        System.out.println("binary search -> index " + idxBin + " in " + binNanos / 1_000 + " us");
        System.out.println("first occurrence of target: " + firstOccurrence(arr, target));
    }

    static int linearScan(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }

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

    static int firstOccurrence(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1, found = -1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr[mid] == target) { found = mid; hi = mid - 1; }
            else if (arr[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return found;
    }
}

2. Compile, run, and compare the two times — log n vs n on your own CPU:

javac SearchLab.java
java SearchLab

3. Notice the two index results can differ: random ints repeat, so binarySearch returns a match while firstOccurrence returns the leftmost. You just saw why the boundary variant exists.

4. Break it — infinite loop family. In binarySearch, change lo = mid + 1 to lo = mid. Run again. It hangs on some targets. Add a System.out.println(lo + " " + hi) inside the loop, watch the range stop shrinking, feel the bug, fix it back.

5. Break it — off-by-one family. Change hi = arr.length - 1 to hi = arr.length. Search for a value bigger than everything in the array (binarySearch(arr, Integer.MAX_VALUE)). Read the ArrayIndexOutOfBoundsException and explain to yourself which line of the promise you broke.

6. Extend it — the Koko move. Add minEatingSpeed and canFinish from the lesson, call it with piles = {3, 6, 7, 11} and h = 8, and verify it prints 4. Then trace by hand why speed 3 fails and speed 4 works — that hand-trace is the interview answer.

Problems To Solve

The rule: solve until you can write the template from memory; if stuck 25 min, read the approach, close it, re-solve from scratch.

Check Yourself

1. State the binary search invariant in one sentence.
2. Why lo + (hi - lo) / 2 instead of (lo + hi) / 2? What exactly goes wrong, and at what kind of values?
3. Name the three bug families. Which one makes the program hang rather than crash or return wrong answers?
4. In firstOccurrence, why do you set hi = mid - 1 after finding the target instead of returning?
5. In the Koko template, why is the update hi = mid instead of hi = mid - 1 — and why must the loop condition then be lo < hi?
6. What property must the answer space have for binary-search-on-the-answer to work?
7. Roughly how many steps does binary search take on one billion elements, and why?
8. A problem gives you a sorted array and asks for a pair summing to a target. Why is binary search not the best tool, and what is?

Explain it out loud: Explain to the empty chair how you’d find a bad deploy among 500 commits in 9 checks, then how the same idea finds Koko’s minimum eating speed — making the false-false-true-true picture the bridge between them. If you can’t connect the two, re-read the answer-space section.

Still Unclear?

I'm learning binary search. Give me 4 short Java binary search implementations,
each hiding exactly one bug from these families: off-by-one, infinite loop,
wrong boundary update, integer overflow in mid. Make me find and name each bug
before you confirm. Do not fix them for me.

Walk me through Koko Eating Bananas WITHOUT code: only the false-false-true-true
picture over eating speeds. Then give me two new problems that look nothing like
bananas and make me identify what the answer space is, what the feasibility
check is, and why monotonicity holds, before any code is written.

My firstOccurrence binary search returns a correct index on some inputs and -1
on others where the value exists. Using only the invariant - the answer is
always inside lo..hi - interrogate me step by step about my update rules until
I find which update breaks the promise.

Why AI Can’t Do This For You

AI writes a perfect binary search in one second — the template is in every training set. What it can’t do is sit in your interview when the question is “minimum days to ship all packages” and no array is in sight, and fire the recognition: monotonic condition, search the answer space. That leap from problem-wording to pattern is the entire game, and it only happens in a head that has drilled it.

Same on the job: when a query is slow, when bisecting 500 commits at 2 a.m., when a timestamp window needs slicing — nobody hands you a problem labeled “binary search.” You either see the sorted, monotonic structure hiding in the mess, or you write the O(n) scan and become the next module’s cautionary tale. Pattern recognition under pressure is not promptable.

Module done? Add it to today’s tracker