Three templates. Every binary search. Ship it.

What This Is

You're searching for a specific value in a sorted array. The answer is a concrete index — either you find it or you don't.

The Core Insight

Imagine you're looking for page 350 in a book. You don't start at page 1. Instead, you open to the middle, check if you're before or after page 350, then throw away half the book and repeat. Each time you eliminate half the remaining pages. That's binary search.

The key: maintain a closed interval [lo, hi] that always contains your answer (or is empty if it doesn't exist). Check the middle, shrink the interval by moving lo or hi past mid, and stop when lo > hi.

Why "Closed" Interval?

A closed interval means both endpoints are included in the search space. So while (lo <= hi) — the loop exits when lo > hi, meaning the interval is empty and the value isn't there.

The Three Cases at Each Step

1. Found it: nums[mid] == target → return mid immediately.
2. Target is to the right: nums[mid] < target → discard the left half by settinglo = mid + 1.
3. Target is to the left: nums[mid] > target → discard the right half by settinghi = mid - 1.

Why mid+1 and mid-1?

Because we've already checked nums[mid]. It's not the target, so don't include it in the next search. If you use lo = mid or hi = mid, you'll check the same element again → infinite loop.

When to Use This

• Sorted array, find an exact value or its index
• Problem says "does X exist?" or "find the index of X"
• You need O(log n) — linear search is too slow

⚠️ Gotchas That Will Burn You

• Wrong loop condition: If you write while (lo < hi) with hi = mid (without the -1), you're using a half-open interval [lo, hi). Different template. Stick with one.
• Integer overflow: In Java/C++, (lo + hi) / 2 can overflow. Use lo + (hi - lo) / 2. Python handles big ints automatically.
• Off-by-one: Test with arrays of size 0, 1, 2. Many bugs hide in edge cases.
• Not returning -1: After the loop exits, lo > hi means the value isn't there. Return -1 (or whatever "not found" means in your problem).

What This Is

You're not looking for an exact value. Instead, you're looking for the first index where a condition becomes true. The condition is monotonic: it's false for some indices, then becomes true for all remaining indices.

Real-World Analogy

You have a pile of cookies. Some are fresh (good), some are stale (bad). You want to find the first stale cookie. The pile is sorted: all fresh ones come first, then all stale ones. You don't need the exact position of a specific stale cookie — you just need the leftmost (first) one.

The Key Difference: Half-Open Interval

Template B uses while (lo < hi) with a half-open interval [lo, hi). When the loop exits,lo == hi and it points to the answer. You don't need to check separately for "not found" in most cases.

The Two Cases at Each Step

1. Condition is TRUE at mid: The answer might be at mid or to its left. Don't skip mid; sethi = mid to keep it in the search space.
2. Condition is FALSE at mid: The answer is strictly to the right. Set lo = mid + 1 to skip mid.

Why Does This Work?

Because the condition is monotonic, once you find a TRUE value, you know the answer is there or to its left. By setting hi = mid, you keep it in the search space. Meanwhile, when you find a FALSE value, the answer must be to the right, so lo = mid + 1 safely skips it.

The loop terminates when lo == hi, and that index is guaranteed to be the leftmost (first) index where the condition is true.

When to Use This

• "Find the first / leftmost / minimum index where..."
• "Find the first element ≥ X" (lower_bound)
• "Find the insert position to keep the array sorted"
• Any problem with a monotonic yes/no condition

⚠️ Gotchas That Will Burn You

• Wrong loop condition: while (lo < hi), not lo <= hi. The loop stops whenlo == hi, which is the answer.
• Assignment mistake: When condition is true, set hi = mid (not mid-1). When false, setlo = mid + 1. These are different from Template A!
• Not verifying monotonicity: The condition MUST be monotonic (all false, then all true). If it flips back and forth, binary search doesn't work. State this in your interview.
• Forgetting the "not found" case: If nothing matches, lo will point to the first position where the condition is true, which might be out of bounds or a sentinel value.

What This Is

There's no sorted array to search. Instead, the answer itself is a number in a known range, and you can check whether a candidate answer is feasible. Use binary search to find the smallest (or largest) feasible answer.

The Paradigm Shift

Template A and B search an array. Template C searches a range of possible answers. Instead of checking if a value exists in the input, you ask: "Is this candidate answer feasible?" If yes for some k and no for k-1, binary search finds the boundary.

Real-World Analogy

You want to find the minimum speed to finish eating all bananas within h hours. You can't check "speed 5" by looking it up in an array. Instead, you write a function that simulates eating at speed 5 and checks if it finishes in time. Then you binary search over the range [1, max(pile)].

The Crucial Requirement: Monotonicity of Feasibility

If answer A is feasible, then any answer ≥ A is also feasible. (Faster eating never makes you slower. Higher capacity never makes you fail.) This monotonicity is what makes binary search valid.

The Setup

1. Define the answer range: lo = minimum possible answer, hi = maximum possible answer.
2. Write feasible(mid) that checks if the candidate answer works.
3. Use Template B's shape: while (lo < hi), set hi = mid if feasible, else lo = mid + 1.
4. Return lo — the smallest feasible answer.

Why Template B's Shape?

Because you're searching for the "minimum feasible answer" — the leftmost position where feasibility becomes true. That's exactly what Template B finds.

When to Use This

• "Minimize the maximum" / "maximize the minimum"
• "Find the smallest X such that..."
• "Find the minimum/maximum capacity/speed/days/..."
• Any problem where the answer is a number you can test for feasibility

⚠️ Gotchas That Will Burn You

• Forgetting to state monotonicity: Always prove it out loud: "If X works, then X+1 works because..." This shows you understand why binary search applies.
• Wrong answer range: lo must be the absolute minimum (e.g., speed 1). hi must be large enough to be feasible (e.g., max(piles)). If you set them wrong, you miss the answer.
• Slow feasible() function: If feasible(mid) is O(n) and you call it O(log n) times, total complexity is O(n log n). Acceptable, but mention it.
• Confusion with minimize vs. maximize: "Minimize the maximum" → search for the smallest answer where all constraints are satisfied. "Maximize the minimum" → flip the feasible check. Be precise.