08 — Binary Search

The core idea

Most people learn binary search as "search a sorted array". That framing is too narrow and it's why the harder variants feel like different problems. The real definition:

There is a predicate that is false, false, …, false, true, true, …, true over some ordered space, and you want the boundary.

Each step you test the middle. The result tells you which half the boundary is in, so you throw the other half away. Halving repeatedly means log₂ n steps: for a million elements, 20 steps.

Once you see it as "find the boundary of a monotonic predicate", binary search on the answer stops being a trick and becomes the natural reading.

Three uses across the 150:

1. Search an index space — classic, plus rotated variants.
2. Search an answer space — the array isn't what you search; the candidate answers are.
3. Search a partition — Median of Two Sorted Arrays.

Template A — exact match

int lo = 0, hi = nums.length - 1;            // INCLUSIVE on both ends
while (lo <= hi) {                            // <= because lo == hi is still a live candidate
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) lo = mid + 1;     // target is to the right
    else hi = mid - 1;                        // target is to the left
}
return -1;

Trace: find 7 in [1, 3, 5, 7, 9, 11].

The two conventions — pick one and never mix them

Almost every binary search bug is a mismatch here.

What goes wrong when you mix them:

• lo < hi with hi = mid - 1 → the answer can be skipped, since mid gets discarded while lo may already equal it.
• lo <= hi with hi = mid → infinite loop. When lo == hi, mid == lo, and hi = mid changes nothing. The loop spins forever.

Why mid = lo + (hi - lo) / 2

(lo + hi) / 2 looks fine but overflows when lo + hi exceeds ~2.1 billion, wrapping negative and indexing outside the array.

lo + (hi - lo) / 2 computes the same value but only ever evaluates a difference, which always fits. This exact bug lived in the JDK's own Arrays.binarySearch for nine years — interviewers know the story and notice the safe form.

Template B — boundary search

The most reusable form. Returns the first index where a predicate is true, or n if never.

int lo = 0, hi = n;                       // hi is EXCLUSIVE; n means "no such index"
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (predicate(mid)) hi = mid;         // mid MIGHT be the answer — keep it in range
    else lo = mid + 1;                    // mid is definitely not — discard it
}
return lo;                                 // lo == hi == the boundary

Why this never loses the answer: hi = mid (not mid - 1) keeps mid inside the search range whenever it satisfies the predicate. The range shrinks because mid < hi always holds, so hi strictly decreases.

Deriving lower_bound and upper_bound — only the predicate changes:

predicate = (i) -> nums[i] >= target;     // lower bound: first index >= target
predicate = (i) -> nums[i] >  target;     // upper bound: first index >  target

And then count of target = upperBound − lowerBound.

Why not Arrays.binarySearch? It returns an arbitrary matching index when there are duplicates, with no guarantee it's the first or last. For any duplicate-related question, write the boundary search.

Template C — binary search on the answer

Recognizing it

The tell is a combination:

• The question asks for a minimum or maximum value.
• The value range is huge (10^9), but n is modest.
• There's a feasibility check that is monotonic: if k works, every k larger also works.

When you see that, you're not searching the array — you're searching the range of possible answers.

int lo = smallestPossibleAnswer, hi = largestPossibleAnswer;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (feasible(mid)) hi = mid;          // mid works — try smaller
    else lo = mid + 1;                    // mid fails — must go bigger
}
return lo;

Koko Eating Bananas

Koko eats k bananas/hour. Each hour she picks one pile and eats up to k from it (leftovers in a pile wait for the next hour). Given piles and h hours, find the smallest k that finishes in time.

Framing it:

• The candidate answers run from 1 to max(piles) — eating the biggest pile per hour always works.
• Feasibility: "can Koko finish at speed k?" — computable in O(n).
• Monotonic? Yes: if speed 5 finishes in time, so does 6. Faster never needs more hours. That monotonicity is the licence to binary search.

int lo = 1, hi = 0;
for (int p : piles) hi = Math.max(hi, p);

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    long hours = 0;
    for (int p : piles) hours += (p + mid - 1) / mid;   // ceiling division
    if (hours <= h) hi = mid;       // fast enough — try slower
    else lo = mid + 1;              // too slow — must speed up
}
return lo;

Trace: piles = [3, 6, 7, 11], h = 8. Range is [1, 11].

✓

Three things to state:

1. Monotonicity is the precondition. Without it binary search is invalid, no matter how the code looks.
2. (p + mid - 1) / mid is integer ceiling division. Integer division truncates down; adding mid - 1 pushes any remainder up to the next whole hour. Avoid Math.ceil on doubles — floating point rounds unpredictably at large values.
3. Accumulate in a long. 10^4 piles × 10^9 bananas overflows int.

Complexity: O(n log(maxValue)) — the log is over the value range, not the array length. Say it that way; it's the distinguishing feature of this pattern.

Other problems in the 150 with this shape: Swim in Rising Water (feasible = "a path exists at water level t", checked with BFS).

Rotated sorted arrays

A rotated array like [4, 5, 6, 7, 0, 1, 2] is two sorted runs. The key structural fact:

At any mid, at least one half is properly sorted.

Identify which half is sorted, then check whether the target lies inside it.

Find Minimum in Rotated Sorted Array

int lo = 0, hi = nums.length - 1;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (nums[mid] > nums[hi]) lo = mid + 1;   // pivot is strictly right of mid
    else hi = mid;                            // mid could BE the minimum
}
return nums[lo];

Trace on [4, 5, 6, 7, 0, 1, 2]:

Compare with nums[hi], never nums[lo]

This is the most common bug in the rotated family.

Why nums[hi] works: if nums[mid] > nums[hi], then mid is in the first (higher) run and the wrap-around point must be to its right. Otherwise mid is in the second run, and the minimum is at mid or left of it.

Why nums[lo] fails: on a non-rotated array like [1,2,3,4,5], nums[mid] > nums[lo] is true — so you'd search right and miss the minimum sitting at index 0. Comparing against hi handles rotated and non-rotated uniformly.

Search in Rotated Sorted Array

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

    if (nums[lo] <= nums[mid]) {                        // LEFT half is sorted
        if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;   // inside it
        else lo = mid + 1;                                            // outside it
    } else {                                            // RIGHT half is sorted
        if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
        else hi = mid - 1;
    }
}
return -1;

Reading it: first decide which half is sorted. Then, within that sorted half, you can test membership with simple range comparisons — because sorted means "between the endpoints" is exactly "present in this range".

Two details:

• nums[lo] <= nums[mid] uses <= to handle the two-element case where lo == mid.
• The bounds are asymmetric (nums[lo] <= … < nums[mid] on one side, nums[mid] < … <= nums[hi] on the other). Each uses the closed end of its sorted half, since nums[mid] was already tested for equality.

2-D as a flattened 1-D array

When each row is sorted and every element of a row precedes the next row's, the matrix is one sorted array. You just need index arithmetic.

int rows = matrix.length, cols = matrix[0].length;
int lo = 0, hi = rows * cols - 1;

while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    int val = matrix[mid / cols][mid % cols];        // the whole trick
    if (val == target) return true;
    if (val < target) lo = mid + 1;
    else hi = mid - 1;
}
return false;

How mid / cols and mid % cols work: treat the matrix as a single array read left-to-right, top-to-bottom. Flat index 7 in a 3-column matrix is row 7 / 3 = 2, column 7 % 3 = 1.

flat:   0  1  2 | 3  4  5 | 6  7  8
row:    0  0  0 | 1  1  1 | 2  2  2      <- index / 3
col:    0  1  2 | 0  1  2 | 0  1  2      <- index % 3

Divide by the COLUMN count, not the row count. Swapping them is the standard bug, and it produces plausible-looking results on square matrices before failing on rectangular ones.

One O(log(m·n)) search. The two-stage "find the row, then search within it" version has the same complexity but more code and more edge cases.

Binary search inside a hash map (Time Based Key-Value Store)

set(key, value, timestamp) then get(key, timestamp) returns the value with the largest timestamp ≤ the query.

Since timestamps arrive increasing, each key's list is already sorted — binary search it with the "floor" idiom.

private Map<String, List<int[]>> store = new HashMap<>();   // key -> [{timestamp, valueIdx}]

public String get(String key, int timestamp) {
    List<int[]> list = store.getOrDefault(key, List.of());
    int lo = 0, hi = list.size() - 1;
    String res = "";
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (list.get(mid)[0] <= timestamp) {
            res = valueAt(list.get(mid));     // a valid candidate — remember it
            lo = mid + 1;                     // but look for a LATER one
        } else {
            hi = mid - 1;                     // too late — go earlier
        }
    }
    return res;
}

The "remember the best candidate, keep searching right" idiom is the floor query. When mid qualifies, it's an answer but maybe not the best one, so record it and keep pushing right.

TreeMap.floorEntry does this in one call (02). Mention it as the production answer, then write the binary search — the question is testing the mechanic.

Median of Two Sorted Arrays

The one genuinely hard binary search in the 150. Required: O(log(m+n)).

The reframe

You are not searching for a value. You are searching for a partition point.

The median splits all m + n elements into a left half and a right half of (nearly) equal size, where everything on the left ≤ everything on the right.

So: cut nums1 after i elements and nums2 after j elements, such that:

• i + j = half the total (the left side holds half), and
• max(left side) <= min(right side).

Because i + j is fixed, choosing i forces j. So there's only one variable — binary search it.

nums1:  a[0] a[1] ... a[i-1] | a[i] ... a[m-1]
nums2:  b[0] b[1] ... b[j-1] | b[j] ... b[n-1]
        \________left________/ \______right______/

Valid when a[i-1] <= b[j] and b[j-1] <= a[i] (the cross-comparisons).

if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);

int m = nums1.length, n = nums2.length;
int half = (m + n + 1) / 2;                 // +1 puts the extra element on the LEFT when odd
int lo = 0, hi = m;

while (lo <= hi) {
    int i = lo + (hi - lo) / 2;             // take i elements from nums1
    int j = half - i;                       // ...so j from nums2 is forced

    int left1  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
    int right1 = (i == m) ? Integer.MAX_VALUE : nums1[i];
    int left2  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
    int right2 = (j == n) ? Integer.MAX_VALUE : nums2[j];

    if (left1 <= right2 && left2 <= right1) {          // valid partition found
        if ((m + n) % 2 == 1) return Math.max(left1, left2);
        return (Math.max(left1, left2) + Math.min(right1, right2)) / 2.0;
    }
    if (left1 > right2) hi = i - 1;         // took too many from nums1
    else lo = i + 1;                        // took too few
}
throw new IllegalArgumentException("input arrays are not sorted");

Trace: nums1 = [1, 3], nums2 = [2]. After the swap, nums1 = [2] (shorter), nums2 = [1, 3]. m=1, n=2, half = (1+2+1)/2 = 2.

Total is odd (3), so return max(left1, left2) = max(2, 1) = 2. ✓

Four mechanics doing the work

1. Search the shorter array. The swap on line 1 guarantees j = half - i never falls outside nums2. Without it, j can go negative or past the end.
2. ±INFINITY sentinels at the edges remove every "one side is empty" special case. An empty left side has −∞ as its max, which never blocks a comparison.
3. (m + n + 1) / 2 puts the extra element on the left when the total is odd, so the odd answer is just max(left1, left2) with no further branching.
4. / 2.0, not / 2. Integer division would silently truncate the even case.

Recognition checklist

Debugging binary search

When it loops forever or is off by one, check in this order:

1. Do the loop condition and the updates match one convention? (<= with mid ± 1, or < with hi = mid.) This is the cause about 80% of the time.
2. Can a pointer fail to move on some branch? hi = mid is safe only with lo < hi, because mid < hi is then guaranteed.
3. Is mid computed as lo + (hi - lo) / 2?
4. Is the predicate actually monotonic over the search space? If it isn't, binary search is simply the wrong tool — no amount of index fixing will save it.

Complexity summary