Binary Search: Deriving the Optimal Solution for 5 Problems (LC 704/33/153/875/4)

Binary search is the "looks easiest, gets written wrong most often" algorithm. Is the while condition < or <=? Should hi become mid or mid-1? Get one wrong and you loop forever or miss the answer.

This post kills a myth: the precondition for binary search isn't "the array is sorted" — it's "the answer space is monotonic." As long as you can define a yes/no predicate that changes monotonically with the search variable, you can binary-search it. Continuing the full derivation flow:

📋 Problem → 🧭 break down → brute force → bottleneck → insight → optimum → code

• The standard template (704) → searching a rotated array (33) → finding the pivot/minimum (153) → binary-searching the answer (875) → partitioning two arrays (4)

① LC 704 — Binary Search

📋 Problem: Given an ascending, duplicate-free integer array nums and a target, return its index, or -1 if absent. O(log n) required.

Example: nums = [-1,0,3,5,9,12], target = 9 → 4; target = 2 → -1

🧭 From reading the problem to the solution

1. Break it down: sorted, O(log n) — the textbook prototype of binary search.
2. Brute force: a linear scan, O(n), but it wastes the "already sorted" condition.
3. Key insight: looking at the midpoint lets you halve the search range each time — if nums[mid] is smaller than target, the answer is on the right; larger, on the left.
4. Optimum: keep a closed interval [lo, hi] and converge while lo <= hi. Burn this template into muscle memory — the next four problems are all variations of it.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:                  # closed interval [lo, hi]
        mid = lo + (hi - lo) // 2    # avoid overflow
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;     // avoid overflow
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

• Complexity: O(log n) time, O(1) space.
• Pitfall: ① use mid = lo + (hi-lo)/2, not (lo+hi)/2, to avoid overflow; ② a closed interval pairs with lo <= hi and hi = mid - 1 — keep all three consistent, mixing them breaks.

② LC 33 — Search in Rotated Sorted Array

📋 Problem: An ascending array is rotated at some unknown pivot (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]), no duplicates. Find target's index in O(log n).

Example: nums = [4,5,6,7,0,1,2], target = 0 → 4; target = 3 → -1

🧭 From reading the problem to the solution

1. Break it down: not globally sorted, but it's two ascending runs stitched together.
2. Find the pivot first, then binary-search? That works but scans twice. Can we do it in one binary search?
3. Key insight: after taking the midpoint, at least one of [lo, mid] and [mid, hi] is fully sorted. Detect which half is sorted, check whether target falls within that sorted half's range, and you know which way to go.
4. Optimum: use nums[lo] <= nums[mid] to test whether the left half is sorted, then handle the two cases.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:               # left half is sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                                    # right half is sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

int search(vector<int>& nums, int target) {
    int lo = 0, hi = nums.size() - 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;
            else lo = mid + 1;
        } else {                                // right half is sorted
            if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
            else hi = mid - 1;
        }
    }
    return -1;
}

• Complexity: O(log n) time, O(1) space.
• Pitfall: test the sorted half with nums[lo] <= nums[mid] (inclusive), since lo == mid still counts as left-sorted. Always bracket target with the two ends of the sorted half — don't go by gut.

③ LC 153 — Find Minimum in Rotated Sorted Array

📋 Problem: Same rotated, ascending, duplicate-free array — find the minimum, in O(log n).

Example: nums = [3,4,5,1,2] → 1; nums = [4,5,6,7,0,1,2] → 0

🧭 From reading the problem to the solution

1. Break it down: the minimum is the pivot — the position smaller than its predecessor.
2. Brute force: scan for the min, O(n), ignoring the structure.
3. Key insight: compare nums[mid] against the right end nums[hi]. If nums[mid] > nums[hi], the pivot is to the right of mid (the right side "dropped"), so the min is in (mid, hi]; otherwise it's in [lo, mid] (mid included).
4. Optimum: there's no explicit target — this is a "find the boundary" binary search, using lo < hi with hi = mid (not mid-1, since mid itself may be the answer).

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:                  # converge to a single index
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:    # min is strictly to the right of mid
            lo = mid + 1
        else:                        # min is at mid or to its left
            hi = mid
    return nums[lo]

int findMin(vector<int>& nums) {
    int lo = 0, hi = nums.size() - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) lo = mid + 1;   // min is to the right
        else hi = mid;                            // min is at mid or left
    }
    return nums[lo];
}

• Complexity: O(log n) time, O(1) space.
• Pitfall: ① compare against nums[hi], not nums[lo] — comparing to the left end misjudges the non-rotated case; ② use lo < hi (not <=) with hi = mid, or you loop forever. This is the canonical "find a boundary" form, distinct from 704's "find an exact value" form.

④ LC 875 — Koko Eating Bananas

📋 Problem: There are piles of bananas. Each hour Koko picks one pile and eats at speed k (bananas/hour); if a pile has fewer than k left, she finishes it and waits out the hour. Given a deadline of h hours, find the minimum integer speed k that lets her finish within h hours.

Example: piles = [3,6,7,11], h = 8 → 4; piles = [30,11,23,4,20], h = 5 → 30

🧭 From reading the problem to the solution

1. Break it down: find the "smallest feasible k." The array doesn't even need sorting — this binary search isn't over the array.
2. Brute force: try k = 1 upward until it finishes within h, O(max(piles) · n). Too slow.
3. Key insight (binary-search the answer): define a predicate canFinish(k) = "can speed k finish within h hours?" Faster speed → less time, so canFinish(k) is monotonic in k (false…false then true…true). We want the first true. A monotonic predicate is all you need to binary-search — no sorted array required.
4. Optimum: binary-search the answer range [1, max(piles)], evaluating feasibility with a sum of ceil(pile/k) hours.

def minEatingSpeed(piles, h):
    def hours(k):                       # hours needed at speed k
        return sum((p + k - 1) // k for p in piles)   # ceil division
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours(mid) <= h:             # feasible → try a slower speed
            hi = mid
        else:                            # too slow → must speed up
            lo = mid + 1
    return lo

int minEatingSpeed(vector<int>& piles, int h) {
    auto hours = [&](int k) {
        long long t = 0;
        for (int p : piles) t += (p + k - 1) / k;     // ceil division
        return t;
    };
    int lo = 1, hi = *max_element(piles.begin(), piles.end());
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (hours(mid) <= h) hi = mid;    // feasible → slower
        else lo = mid + 1;                // too slow → faster
    }
    return lo;
}

• Complexity: O(n · log(max(piles))) time, O(1) space.
• Pitfall: ① binary-search the answer space (speed), not the input array; ② write ceil(p/k) as (p + k - 1) // k; ③ the lower bound is 1, not 0 (division by zero); ④ get the monotonic direction right: feasible → move toward smaller k (hi = mid).

💡 Recognition signal: a problem asking for "the smallest k that can… / the largest that doesn't exceed…" with a monotonic feasibility check is almost always "binary-search the answer." Same family: split array largest sum (410), shipping packages (1011).

⑤ LC 4 — Median of Two Sorted Arrays

📋 Problem: Given two ascending arrays A, B, return the median of their merge, in O(log(m+n)).

Example: A = [1,3], B = [2] → 2.0; A = [1,2], B = [3,4] → 2.5

🧭 From reading the problem to the solution

1. Break it down: O(log) is required, so "merge then sort and take the middle" (O(m+n)) or two-pointer merge is too slow.
2. Bottleneck: the median splits the merged array into a left half and a right half where every left ≤ every right and the left half has a fixed length. The catch: we don't want to actually merge.
3. Key insight (binary-search the cut): once you decide "where to cut A" (i elements go to the left half), B's cut j is uniquely forced by the left-half length (m+n+1)//2. A correct cut must satisfy A[i-1] ≤ B[j] and B[j-1] ≤ A[i] (max of left ≤ min of right). If i is too big, move left; too small, move right — monotonic in i, so binary-searchable.
4. Optimum: binary-search i on the shorter array (guaranteeing O(log(min(m,n)))), using ±∞ sentinels for the edges.

def findMedianSortedArrays(A, B):
    if len(A) > len(B):                 # binary search on the shorter array
        A, B = B, A
    m, n = len(A), len(B)
    half = (m + n + 1) // 2             # size of the left half
    lo, hi = 0, m
    while lo <= hi:
        i = lo + (hi - lo) // 2         # cut in A: i elements on the left
        j = half - i                    # cut in B is forced
        Aleft  = A[i-1] if i > 0 else float('-inf')
        Aright = A[i]   if i < m else float('inf')
        Bleft  = B[j-1] if j > 0 else float('-inf')
        Bright = B[j]   if j < n else float('inf')
        if Aleft <= Bright and Bleft <= Aright:    # correct partition
            if (m + n) % 2:
                return float(max(Aleft, Bleft))    # odd total
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
        elif Aleft > Bright:            # cut A is too far right
            hi = i - 1
        else:                            # cut A is too far left
            lo = i + 1

double findMedianSortedArrays(vector<int>& A, vector<int>& B) {
    if (A.size() > B.size()) swap(A, B);          // search the shorter one
    int m = A.size(), n = B.size(), half = (m + n + 1) / 2;
    int lo = 0, hi = m;
    while (lo <= hi) {
        int i = lo + (hi - lo) / 2;               // cut in A
        int j = half - i;                         // cut in B is forced
        long Aleft  = i > 0 ? A[i-1] : LONG_MIN;
        long Aright = i < m ? A[i]   : LONG_MAX;
        long Bleft  = j > 0 ? B[j-1] : LONG_MIN;
        long Bright = j < n ? B[j]   : LONG_MAX;
        if (Aleft <= Bright && Bleft <= Aright) {
            if ((m + n) % 2) return max(Aleft, Bleft);
            return (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0;
        } else if (Aleft > Bright) hi = i - 1;
        else lo = i + 1;
    }
    return 0.0;
}

• Complexity: O(log(min(m, n))) time, O(1) space.
• Pitfall: ① always binary-search the shorter array, or j can go negative; ② handle the edges (cut at the very left/right) with ±∞ sentinels to drop a pile of ifs; ③ half = (m+n+1)//2 plus returning max(left) for odd totals handles both parities in one shot. This is a Hard — explaining clearly "why the cut is binary-searchable" already wins half the battle.

One Table to Remember It All

Pattern-Recognition Cheats

• "sorted + find a value / find a boundary" → standard binary search; first decide "exact value (lo<=hi)" vs "boundary (lo<hi + hi=mid)."
• "rotated sorted array" → one half is always sorted; detect which, then decide which side to keep.
• "smallest that can… / largest that doesn't exceed… + monotonic feasibility" → binary-search the answer, where the search space is the answer, not the input.
• "two sorted arrays, O(log)" → binary-search the cut, and remember to search the shorter one.

The essence of binary search isn't "the array is sorted" — it's "the answer space is monotonic, so each step halves it." Weld the 704 template into muscle memory, and the other four are just swapping out what you binary-search over.