Classic binary search — sorted array, find index

Recognize it from

“Array is sorted. Return the index of t, or −1.” Variants: first/last occurrence, insert position. Not “binary search the answer” (Koko) — that searches a value domain, not an index.

What it actually does

Each step throws away half of the remaining closed interval [lo, hi]. Compare t to the middle. Equal: done. Smaller: the right half cannot hold t. Larger: the left half cannot. When lo > hi the interval is empty and t was never present.

Simple version is the same idea on the call stack. Interview version is a loop, overflow-safe mid, and lo <= hi so a single remaining cell is tested rather than skipped.

public int search(int[] a, int t) {
    return rec(a, t, 0, a.length - 1);
}
private int rec(int[] a, int t, int lo, int hi) {
    if (lo > hi) return -1; // empty slice: t is not here
    int mid = lo + (hi - lo) / 2;
    if (a[mid] == t) return mid;
    if (a[mid] < t) return rec(a, t, mid + 1, hi); // t lives right of mid
    return rec(a, t, lo, mid - 1);
}

public int search(int[] a, int t) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) { // inclusive: a one-cell window is still a search
        int mid = lo + (hi - lo) / 2; // (lo + hi) / 2 overflows when lo, hi are huge
        if (a[mid] == t) return mid;
        if (a[mid] < t) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Example 1 — simple

Find 3 in [1, 3, 5].

Answer: index 1.

Example 2 — every step

Find 6 in [1, 3, 5, 7] — not present. Every lo / hi until the window dies.

Answer: −1. The last living cell was index 3 (value 7). Shrinking hi to 2 with lo already 3 empties the range. A lo < hi loop with the wrong mid bias can spin here — that is why the interview version keeps <= and always moves lo or hi past mid.

Rotated sorted array — which half is sorted

Recognize it from

“Sorted array rotated at an unknown pivot. Find t.” One half of [lo, mid] or [mid, hi] is still monotonic. That is the invariant. Not circular Kadane (max wrap subarray). Not “find the rotation index” unless they asked only for the min.

What it actually does

A rotation splits the array into two sorted runs. At any mid, at least one of the two closed halves is sorted (unless duplicates collapse both — then shrink lo/hi by one). Ask: is the left half sorted? If yes, decide whether t belongs in that numeric range; if not, throw that half away.

Simple version finds the minimum first (the rotation), then runs ordinary binary search on one of the two runs. Interview version does it in one pass so you do not spend a second log n if they only wanted t.

public int searchRotatedTwoPass(int[] a, int t) {
    int n = a.length;
    int lo = 0, hi = n - 1;
    while (lo < hi) { // find the rotation: smallest element
        int mid = lo + (hi - lo) / 2;
        if (a[mid] > a[hi]) lo = mid + 1; // min lives to the right of mid
        else hi = mid;
    }
    int k = lo; // index of minimum; [0..k) and [k..n) are both sorted
    int inLeft = bsearch(a, t, 0, k - 1);
    if (inLeft >= 0) return inLeft;
    return bsearch(a, t, k, n - 1);
}
private int bsearch(int[] a, int t, int lo, int hi) {
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == t) return mid;
        if (a[mid] < t) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

public int search(int[] a, int t) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == t) return mid;
        if (a[lo] <= a[mid]) { // left closed interval is sorted
            if (a[lo] <= t && t < a[mid]) hi = mid - 1; // t sits inside that sorted run
            else lo = mid + 1;
        } else { // right closed interval is sorted
            if (a[mid] < t && t <= a[hi]) lo = mid + 1; // t sits inside the sorted right run
            else hi = mid - 1;
        }
    }
    return -1;
}

Example 1 — simple

[4, 5, 6, 1, 2], find 1.

Answer: index 3.

Example 2 — every step

[4, 5, 6, 7, 0, 1, 2], find 0. Every mid until the hit.

Answer: index 4. After the first probe you discarded the entire left run [4,5,6,7] with one range check. The second probe’s left half is [0,1] — now the sorted half does contain 0, so you shrink hi onto it.

Binary search on the answer — Koko / ship packages

Recognize it from

“Minimum speed / capacity / days so that a linear pack still finishes by H.” Monotone: if speed k works, every k' > k also works. You search k, not an index in piles. Same skeleton: split array / book allocation (min of max load), aggressive cows (max of min gap, inequality flips).

What it actually does

The piles are not sorted in a way that helps. The answer is monotonic. Set lo = 1 (or max element for ship capacity), hi = max pile (or sum of weights). feasible(mid) is one O(n) scan: hours = sum of ceil(pile / mid). If that is ≤ h, try a slower speed (shrink hi). Else raise lo.

Ship-packages is the same shape with a different feasible: load each weight onto the current day until capacity would overflow, then start a new day; succeed if days ≤ D. Aggressive cows / max-min gap flips the predicate: larger D is harder, so a success tries higher. Integer ceil: (p + k − 1) / k, in long.

public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p); // speed max pile finishes in n hours
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(piles, h, mid)) hi = mid; // mid works: try slower
        else lo = mid + 1;
    }
    return lo;
}
private boolean feasible(int[] piles, int h, int k) {
    int hours = 0;
    for (int p : piles) {
        hours += (int) Math.ceil((double) p / k); // works; float is the thing to drop later
        if (hours > h) return false;
    }
    return hours <= h;
}

public int minEatingSpeed(int[] piles, int h) {
    int lo = 1, hi = 0;
    for (int p : piles) hi = Math.max(hi, p);
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(piles, h, mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}
private boolean feasible(int[] piles, int h, int k) {
    long hours = 0; // n * ceil(pile/k) can exceed int
    for (int p : piles) {
        hours += (p + (long) k - 1) / k; // ceil(p/k) for positive ints, no float
        if (hours > h) return false;
    }
    return hours <= h;
}

Example 1 — simple

piles = [3, 6, 7, 11], h = 8. Why 4 works and 3 does not.

Minimum feasible speed is 4. Heap-of-piles does not replace this: you are not repeatedly eating from the current largest pile; you pick one constant speed for every hour slot.

Example 2 — every step

Same instance. lo = 1, hi = 11, loop while (lo < hi), hi = mid on success. Every mid until lo == hi.

Answer: 4. Ship-packages on the same numbers would change lo to max(weight) and feasible to “days at capacity mid.” The mid table looks different; the loop skeleton does not.

See also

Classic search and rotated search still probe an array index. Koko probes a number you will return. If the prompt is “possible or impossible at budget T” and larger T is easier (or strictly harder), you are on the third card. Server-partition assignment with a min-heap of loads is not this — that is a greedy heap, in chapter 05 of the notebook, not a binary search.