Binary Search Complete Guide — All Patterns, Templates, and 23 LeetCode Problems

Problem Statement#

A complete pattern-driven guide to binary search interview problems, organised from easy to hard with reusable Python and JavaScript templates.

Constraints:

• 23 problems numbered 00–22 in this series
• Difficulty mix: easy 8, medium 12, hard 3
• All problems use binary search either on the data or on the answer space

Input:  Sorted or partially structured array + a question
Output: Index, value, count, or boolean — found in O(log n) or O(n log M)

Input:  Monotone predicate over an integer range [lo, hi]
Output: Smallest or largest value satisfying the predicate

Why This Problem Matters#

Binary search is the most asked algorithmic technique in FAANG interviews after hashing. Google, Amazon, Meta, Microsoft, and Apple all use binary search problems in phone screens, onsite rounds, and bar-raiser sessions. The reason is simple: binary search separates engineers who can recognise structure from engineers who only know how to scan.

The deeper truth most candidates miss is that binary search is not about searching arrays. It is about logarithmic exploration of any monotone decision space. Once you internalise that idea, you stop searching arrays and start searching answers — minimum eating speed, smallest ship capacity, largest k satisfying a condition. This shift from "search the data" to "search the answer" unlocks an entire tier of medium and hard interview questions.

This guide indexes 23 problems built around the FAANG binary search interview funnel. Master the templates here and the rest of the series compounds quickly — every problem reuses one of seven patterns below.

The Core Insight#

Binary search works whenever you can make a definitive binary decision at each midpoint that shrinks the search space by half. The data does not need to be sorted globally — it needs a monotone predicate.

Visual Dry Run#

Solution (Optimal)#

# Universal left-boundary template — first index where condition is true
def left_boundary(lo, hi, condition):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):
            hi = mid           # answer could be mid
        else:
            lo = mid + 1       # answer is strictly after mid
    return lo                  # lo equals hi equals first true position
 
# Universal right-boundary template — last index where condition is true
def right_boundary(lo, hi, condition):
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # upper-mid prevents infinite loop
        if condition(mid):
            lo = mid           # answer could be mid
        else:
            hi = mid - 1       # answer is strictly before mid
    return lo
 
# Binary search on answer — minimise integer satisfying feasibility
def bs_on_answer(lo, hi, feasible):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid           # try a smaller answer
        else:
            lo = mid + 1       # need a larger answer
    return lo

// Universal left-boundary template
function leftBoundary(lo, hi, condition) {
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (condition(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}
 
// Universal right-boundary template (upper-mid)
function rightBoundary(lo, hi, condition) {
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo + 1) / 2);
        if (condition(mid)) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    return lo;
}
 
// Binary search on answer
function bsOnAnswer(lo, hi, feasible) {
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (feasible(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
}

Time: O(log n) for array search, O(n log M) for binary search on answer where M is the answer range. Space: O(1) — only three integer variables.

Common Mistakes#

• Using (lo + hi) / 2 in Java/C++ — overflows when both values are large; always use lo + (hi - lo) / 2.
• Mixing templates — picking while lo lessequal hi with hi = mid causes infinite loops.
• Forgetting upper-mid for right-boundary — lo = mid paired with lower-mid loops forever when lo == hi - 1.
• Wrong initial hi — for insert-position style problems, set hi = len(nums) not len(nums) - 1.
• Not validating the predicate is monotone — binary search silently returns garbage on non-monotone inputs.

Interview Tips#

• State the loop invariant aloud before coding: "the answer always lies in [lo, hi]."
• Pick a template and commit — never mix <= and < mid-solve.
• Always show a dry run on a small input to catch off-by-one before submitting.
• For binary search on answer, name the predicate explicitly: feasible(mid).
• Mention overflow handling for static-typed languages even if writing Python.

Follow-up Questions#

• How would you adapt this to find the kth smallest element in a multiset? Hint: binary search on value range with count predicate.
• Can binary search work on a function we can only sample, not store? Yes — that is exactly what LC 278 First Bad Version does.
• How do you binary search a 2D matrix without flattening? Use staircase search when only rows and columns are sorted independently.
• What happens with duplicates in a rotated array? Worst case degrades to O(n) — see LC 81 and LC 154.

Key Takeaways#

• Binary search reduces any monotone decision problem from O(n) to O(log n) or O(n log M).
• Three templates cover 95 percent of FAANG questions: exact match, left boundary, right boundary.
• Binary search on answer space is the most powerful pattern — apply it whenever the question says "minimum X such that ..." or "maximum X such that ...".
• Always use lo + (hi - lo) / 2 for the midpoint to prevent integer overflow.
• The right-boundary template requires upper-mid lo + (hi - lo + 1) / 2 paired with lo = mid.
• Rotated sorted arrays still admit O(log n) search by checking which half is sorted at each step.
• Duplicates can degrade rotated search to O(n) — be honest about this trade-off in interviews.

Problem Index — Binary Search Series#

Easy (00–04)#

Medium (05–21)#

Hard (22)#