Binary Search & Binary Reduction

Binary search looks like the easiest algorithm on the syllabus and produces some of the most reliable interview failures: infinite loops, off-by-one exits, and the wrong answer on a two-element array. This first session builds one loop template that eliminates the entire bug class — while (left + 1 < right) — and then stretches it across every binary-search question family: first/last occurrence, rotated arrays, 2D matrices, unbounded arrays, and binary search on the answer space itself.

Before the Algorithm: How to Answer Any Interview Question

The session opens with a framework that applies to every coding question, not just this one. It is worth memorizing because interviewers grade the process as much as the code:

1. Clarify — restate the problem, pin down input ranges, duplicates, sortedness, and expected output.
2. Approach — say the candidate approaches out loud, compare, and choose one deliberately.
3. Function signature — write input, output, and helper signatures before the body.
4. Assumptions — enumerate corner cases, edge cases, and base cases up front.
5. Comment, code, review — sketch comments first, fill in code, then trace an example.
6. Complexity — close with time and space, unprompted.

Everything below is that framework applied to one algorithm family. Watch how often step 4 — corner cases — is where the actual difficulty of binary search lives.

When Does Binary Search Apply?

The reflex answer is "when the array is sorted." The correct answer is stronger: binary search applies whenever there is a pattern that lets you discard half the search space each step. Sortedness is just the most common such pattern.

The purest mental model is a boolean sequence:

1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
              ↑
              find the first 0 — no "sorted array" in sight,
              but every probe discards half the space

Any question you can rephrase as "find the boundary where a monotone predicate flips" is a binary search question. First Bad Version is literally this picture (F F F F T T T T). Sqrt(x) is this picture over mid > x/mid. Wood Cut is this picture over "can we cut k pieces of this length?" Once you see the flip-boundary shape, the rest is the template.

One more framing from the notes worth keeping: binary search is the flat version of a binary search tree. The mid-element comparison plays the same role as a BST node comparison — each question you ask prunes one subtree. That connection pays off in Session 5 when BSTs get their own treatment.

The Three Loop Templates — and Why One Wins

There are three standard ways to write the loop, distinguished by their exit condition and how they move the boundaries. They differ in exactly one thing that matters: what state the loop leaves behind.

Template 1: while (left <= right)

Boundaries move past mid: left = mid + 1, right = mid - 1. The loop exits when the pointers cross — right ends up one position left of left. Fine for a pure membership test ("is target present?"), because the moment you see the target you return. Painful for boundary-finding questions, because after the crossover you must reconstruct which position you actually wanted, and the +1/-1 arithmetic is where off-by-one bugs breed.

Template 2: while (left < right)

Exits when left == right — one survivor, which sounds clean, but one case never gets tested inside the loop (the loop condition fails exactly when the two pointers meet). You end up special-casing the final element, and mixing left = mid + 1 with right = mid correctly requires more care than it looks.

Template 3: while (left + 1 < right) — the one to memorize

int left = 0, right = nums.length - 1;
while (left + 1 < right) {
    int mid = left + (right - left) / 2;  // overflow-safe, never (left+right)/2
    if (condition(mid)) {
        right = mid;   // no +1 / -1 anywhere — mid itself stays a candidate
    } else {
        left = mid;
    }
}
// post-processing: exactly two candidates remain, adjacent to each other
if (isAnswer(left))  return left;
if (isAnswer(right)) return right;
return -1;

The loop exits when left and right are adjacent. Because both assignments are plain left = mid / right = mid, the window shrinks strictly every iteration — an infinite loop is structurally impossible, and since mid is never excluded, you can never skip over the answer. The cost: the loop doesn't finish the job. Two candidates survive, and you must check both in post-processing. That trade is excellent, because the post-check is the same two lines in every problem, while +1/-1 reasoning is different in every problem.

The Template in Action: First Bad Version & Guess Number

LC 278 First Bad Version is the flip-boundary picture verbatim: versions are F F F F T T T T and you want the first T. Watch how little code the template needs:

public int firstBadVersion(int n) {
    int left = 1, right = n;
    // F F F F F F F T T T T T T T T T — find the first T
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) right = mid;   // mid could be the first bad → keep it
        else                    left = mid;
    }
    return isBadVersion(left) ? left : right;
}

LC 374 Guess Number Higher or Lower is the same skeleton with a three-way comparison instead of a boolean — guess(mid) returns 0/1/-1 and the 0 case returns early. If you can write LC 278 from muscle memory, LC 374 is a variable rename.

First & Last Occurrence (LC 34)

Search for a Range asks for the first and last index of a target in a sorted array with duplicates. Two clean solutions, both O(log n):

• Twice through the template — one pass biased left (on equality, right = mid) to find the first occurrence, one pass biased right (left = mid) to find the last.
• The firstEqualOrGreater trick — write one helper that finds the first index with nums[i] >= target. Then the range is simply [ f(target), f(target + 1) − 1 ]. One helper, two calls, no duplicate logic.

public int[] searchRange(int[] nums, int target) {
    if (nums == null || nums.length == 0
        || nums[0] > target || nums[nums.length - 1] < target)
        return new int[]{-1, -1};

    int start = firstEqualOrGreater(nums, target);
    if (nums[start] != target) return new int[]{-1, -1};  // e.g. [5,7,8], target 6

    return new int[]{start, firstEqualOrGreater(nums, target + 1) - 1};
}

private int firstEqualOrGreater(int[] nums, int target) {
    int left = 0;
    int right = nums.length;      // NOT length-1: target+1 may exceed everything ([1], target 1)
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid;
        else                    right = mid;
    }
    return nums[left] >= target ? left : right;
}

Boundary Questions: Insert Position & Peak Element

LC 35 Search Insert Position is the template plus a three-way post-processing: after the loop, check nums[start] >= target, then nums[end] >= target, else return end + 1. The note in the original session is worth reproducing exactly: the equality check must stay in the post-processing, because with a tiny array the while loop may never execute at all. Post-processing is not cleanup — it is a full code path.

LC 162 Find Peak Element shows the template working on unsorted data — the predicate is the local slope. If nums[mid] sits on an ascending slope, a peak must exist to the right; descending, to the left; if mid beats both neighbors, return it. With two elements the loop never runs and post-processing (return the larger of start/end) answers directly. Sortedness was never the requirement; a half-discarding argument is.

Reverse Binary Search: When You Can't See the End

Search in a Big Sorted Array (LintCode): the array is sorted but you can only probe by index, and the length is unknown — indexing past the end returns null. You cannot set right = length − 1, so build the right boundary by galloping: start with end = 1 and double it until the probe overshoots (returns null or a value ≥ target). Then run the normal template inside [end/2, end].

S E
_ S _ E
_ _ _ S _ _ _ E
_ _ _ _ _ _ _ S _ _ _ _ _ _ E     // double each round: O(log answer)
                                  // when E overshoots, T is trapped in [S, E]

The doubling phase costs O(log k) where k is the answer's position, so the total stays logarithmic. The same "exponential probe, then binary search" idea shows up in the egg drop discussion: if eggs are precious, walk floor by floor (1 egg, O(n) tests); if tests are precious, probe aggressively and binary search the interval. Recognizing which resource the interviewer wants minimized is the actual question.

Binary Search in 2D (LC 74 & LC 240)

Two matrix-search problems that look alike and are nothing alike:

LC 74 Search a 2D Matrix — each row sorted, and each row's first element greater than the previous row's last. That means the matrix is one sorted array wearing a 2D costume. Binary search over indices 0 … rows×cols−1 and translate: i = mid / cols, j = mid % cols. Pure template, O(log mn), plus the four corner cases (matrix null/empty, matrix[0] null/empty) that the notes flag as the real interview filter.

LC 240 Search a 2D Matrix II — rows sorted and columns sorted, but rows don't chain. It is not a flattened sorted array, and plain binary search dies. The right tool is the staircase walk: start at the top-right corner; if the cell is too small, move down (row++); too big, move left (col--). Every step permanently eliminates a full row or column → O(m + n).

Rotated Sorted Arrays: Casework, Then Template

LC 33 Search in Rotated Sorted Array — a sorted array rotated at an unknown pivot ([4,5,6,7,0,1,2]). The key insight: cut anywhere, and at least one half is still fully sorted. So each iteration asks two questions instead of one: (1) which half is sorted? — compare nums[mid] with nums[left]; (2) is the target inside that sorted half's range? If yes, go there; if no, go to the other half. The template's shape is untouched — only the branch condition grows.

while (left + 1 < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;

    if (nums[mid] > nums[left]) {            // left half [left..mid] is sorted
        if (nums[left] <= target && target < nums[mid])
            right = mid;                     // target inside the sorted half
        else
            left = mid;
    } else {                                 // right half [mid..right] is sorted
        if (nums[mid] < target && target <= nums[right])
            left = mid;
        else
            right = mid;
    }
}
return nums[left] == target ? left : (nums[right] == target ? right : -1);

LC 81 (duplicates allowed) breaks one assumption: when nums[left] == nums[mid] == nums[right], you genuinely cannot tell which half is sorted — the comparison is uninformative. The fix is humble: shrink the window by one (right--) and try again. That single line drops the worst case from O(log n) to O(n) (imagine [1,1,1,1,0,1,1]). Stating that degradation unprompted is a strong-signal moment in interviews.

LC 153 / 154 Find Minimum in Rotated Sorted Array — same family, leaner predicate: compare nums[mid] against nums[right]. Smaller → minimum is at mid or left of it; larger → strictly right of mid. The notes flag the classic trap: compare against right, not left — if the array wasn't rotated at all, the left-comparison walks you away from the minimum. LC 154 adds duplicates, same right-- medicine, same O(n) worst case.

Binary Search on the Answer Space

The most transferable idea of the session. Nothing says the thing you binary search must be an index. Wood Cut (LintCode): given plank lengths and a required piece count k, find the maximum piece length. Observe the monotone predicate: if length L yields ≥ k pieces, every length shorter than L does too — T T T T F F F over the answer's value range. Binary search the length: range [1, max(L)], predicate Σ(Lᵢ / mid) ≥ k, and because we want the largest feasible value, post-processing tests end before start.

LC 410 Split Array Largest Sum — split an array into m consecutive parts minimizing the largest part-sum. Sounds like DP (and has a DP solution), but the answer-space view is cleaner: the answer lies in [max(nums), sum(nums)]; for a candidate cap, a greedy left-to-right pass counts how many parts are forced; feasible caps form a F F T T T boundary. Binary search meets greedy — O(n log(sum)).

public int splitArray(int[] nums, int m) {
    long l = 0, r = 0;
    for (int num : nums) { l = Math.max(l, num); r += num; }  // answer ∈ [max, sum]

    while (l + 1 < r) {
        long mid = l + (r - l) / 2;
        if (feasible(mid, nums, m)) r = mid;   // cap works → try smaller
        else                         l = mid;
    }
    return feasible(l, nums, m) ? (int) l : (int) r;
}

private boolean feasible(long cap, int[] nums, int m) {
    int parts = 1; long total = 0;
    for (int num : nums) {
        total += num;
        if (total > cap) {                // greedy: open a new part only when forced
            total = num;
            if (++parts > m) return false;
        }
    }
    return true;
}

LC 69 Sqrt(x) belongs to the same family in miniature — binary search values 1…x with predicate mid > x / mid (division, not multiplication, to dodge overflow). Three problems, one recipe: value range + monotone feasibility check = binary search.

Binary Search as a Subroutine

The session closes with problems where binary search is a component inside a larger algorithm:

• LC 300 Longest Increasing Subsequence — the O(n log n) solution keeps a tails array (smallest tail for each LIS length) and binary searches the insertion point of each new element. The array being searched is built by the algorithm itself, and stays sorted by construction.
• LC 354 Russian Doll Envelopes — 2D LIS. Sort by width ascending, and height descending on width ties (so equal widths can't chain), then run LIS on heights. The sort trick is the entire problem; the binary search is inherited from LC 300.
• LC 302 Smallest Rectangle Enclosing Black Pixels — given one black pixel in a connected region, binary search each of the four boundaries with an isEmptyRow / isEmptyColumn predicate. Four independent flip-boundary searches, O(m log n + n log m) — dramatically better than flood fill when the image is large.
• LC 275 H-Index II — sorted citations, search the boundary where citations[i] ≥ length − i. A flip-boundary question dressed in academic clothing.

Problem Checklist