Binary Search Master Recap — All Patterns, Templates & FAANG Cheatsheet

Problem Statement#

This is the recap blog for the Binary Search series. It is a single-page cheatsheet you can read end-to-end in 15 minutes the night before your FAANG interview. We cover 45 problems (Easy x 8, Medium x 27, Hard x 10) and distill them into 7 reusable patterns, one universal template, and a decision flowchart for which pattern to apply.

What you get:

• 7 binary-search patterns with init rules and exit conditions
• One universal template that handles all of them
• Binary Search on Answer playbook (the FAANG favorite)
• Big O quick reference
• MAANG priority order to revise problems

Problems covered: 301 - 345 (45 posts)
Difficulty mix:   Easy 8 | Medium 27 | Hard 10
Estimated read:   15 - 20 minutes

Why This Recap Matters#

Binary search shows up in roughly 1 of every 4 FAANG technical screens. It is the single highest leverage topic per minute of study because:

• The same template solves dozens of problems with tiny tweaks.
• "Binary Search on Answer" unlocks otherwise unsolvable optimization problems (Koko, Ship Packages, Aggressive Cows, Painter Partition, Median of Two Sorted Arrays).
• Off-by-one bugs are the #1 reason candidates fail. Memorizing one template eliminates them.

If you only have one night to revise, this page is enough.

The 7 Core Patterns#

The Universal Template#

def binary_search(lo, hi, predicate):
    # Find smallest x in [lo, hi] where predicate(x) is True.
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if predicate(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo  # smallest True, or hi+1 if no True exists

function binarySearch(lo, hi, predicate) {
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (predicate(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
}

Why this works: the predicate must be monotonic. Once it flips from False to True, it stays True. We are finding the boundary.

Binary Search on Answer — The FAANG Favorite#

This is the pattern that separates candidates who memorized BS from candidates who understand it. The trick: instead of searching an array, search the answer space.

Recipe:

1. Identify the answer range. Lower bound is usually 1 or min element. Upper bound is sum or max element.
2. Write a feasible(x) function. Given candidate answer x, can we achieve the goal?
3. Binary search for the smallest (or largest) feasible x.

Problems that use it:

• Koko Eating Bananas — min eating speed
• Capacity to Ship Packages — min ship capacity
• Split Array Largest Sum — min largest subarray sum
• Aggressive Cows — max minimum distance
• Min Days to Make Bouquets — min waiting days
• Magnetic Force Between Two Balls — max minimum force
• Median of Two Sorted Arrays — partition position

Visual Dry Run — BS on Answer (Koko)#

Solution (Universal Template Applied)#

class Solution:
    # BS on answer: smallest k where eating k bananas/hour fits in h hours.
    def minEatingSpeed(self, piles, h):
        def can_finish(k):
            return sum((p + k - 1) // k for p in piles) <= h
 
        lo, hi = 1, max(piles)
        while lo < hi:
            mid = (lo + hi) // 2
            if can_finish(mid):
                hi = mid
            else:
                lo = mid + 1
        return lo

var minEatingSpeed = function(piles, h) {
    const canFinish = (k) => piles.reduce((acc, p) => acc + Math.ceil(p / k), 0) <= h;
    let lo = 1, hi = Math.max(...piles);
    while (lo < hi) {
        const mid = Math.floor((lo + hi) / 2);
        if (canFinish(mid)) hi = mid;
        else lo = mid + 1;
    }
    return lo;
};

Time: O(n log M) where M is max pile Space: O(1)

Big O Quick Reference#

MAANG Priority Order#

If you only have time for 12 problems, do these:

1. Binary Search (704)
2. Search Insert Position (35)
3. First Bad Version (278)
4. Find First and Last Position (34)
5. Search in Rotated Sorted Array (33)
6. Find Minimum in Rotated Sorted Array (153)
7. Search a 2D Matrix (74)
8. Koko Eating Bananas (875)
9. Capacity to Ship Packages (1011)
10. Find Peak Element (162)
11. Median of Two Sorted Arrays (4)
12. Split Array Largest Sum (410)

Common Mistakes#

• Off-by-one in mid calculation. Use lo + (hi - lo) // 2 for lower mid, lo + (hi - lo + 1) // 2 for upper mid (right boundary).
• Wrong loop condition. lo less-equal hi for exact search, lo less than hi for boundary search.
• Forgetting to set hi = mid (not mid - 1) in boundary search. You can lose the answer.
• Picking the wrong answer space in BS on Answer. The lower bound must always be feasible-or-not consistently.
• Not validating monotonicity. If the predicate is not monotonic, binary search does not apply.

Interview Tips#

• State the invariant out loud: "I am searching for the smallest index where predicate is True."
• Always write the predicate as a separate helper. It makes the code reviewable.
• For BS on Answer, justify the bounds explicitly: "Lower bound is 1 because we must eat at least one banana per hour. Upper bound is max(piles) because eating max(piles)/hour finishes any pile in 1 hour."
• Trace through one input on the whiteboard to convince the interviewer your bounds are correct.
• Mention edge cases: empty array, single element, all duplicates.

Follow-up Questions#

• "What if the array is rotated multiple times?" — same as rotated once, modulo n.
• "What if duplicates are allowed?" — degrades to O(n) worst case (LC 81, 154).
• "Can we generalize to ternary search?" — yes, for unimodal functions, but BS is simpler.
• "How would you parallelize BS on Answer?" — partition the answer space across workers.

Key Takeaways#

• One universal template (while lo less than hi; hi = mid; lo = mid + 1) handles 90% of BS problems.
• Binary Search on Answer is the FAANG signature pattern — master the feasibility predicate.
• lo + (hi - lo) // 2 prevents integer overflow vs (lo + hi) // 2.
• Boundary search returns lo (not mid); exact search returns mid when found.
• Rotated array problems reduce to "which half is sorted, is target in it?"
• The hard problems (Median of Two Sorted, Split Array Largest Sum) are still O(log n) per step — never linear scans.
• Always justify your lo and hi initialization out loud during interviews.