Binary Search on Answer: Algorithm Deep Dive

1. Introduction and Core Concepts

Binary search on answer is one of the most powerful yet underappreciated paradigms in algorithm design. While most developers learn binary search as a technique for finding an element in a sorted array, binary search on answer generalizes the idea: instead of searching for an element, we search for the optimal value of an answer within a monotonic search space. This shift in perspective transforms seemingly difficult optimization problems into straightforward decision problems that can be solved efficiently.

At its core, binary search on answer applies when we need to find the minimum or maximum value that satisfies a certain condition, and that condition exhibits monotonicity. Monotonicity means that if a value x is feasible, then all values greater than x (or all values smaller than x, depending on the problem direction) are also feasible. This property creates a sorted-like structure of [False, False, ..., True, True] or [True, True, ..., False, False] over the answer space, which is exactly what binary search needs to operate. The algorithm does not require the input array to be sorted; it requires the predicate function over the answer domain to be monotonic.

Why does this matter? Many real-world optimization problems — from determining the minimum server capacity to handle traffic, to finding the smallest shipment size in logistics, to allocating resources in distributed systems — are difficult to solve directly but easy to verify. It is often hard to compute the optimal answer, but easy to check whether a candidate answer is feasible. Binary search on answer exploits this asymmetry. By combining an efficient feasibility check with binary search over the possible answer range, we can find the optimal solution in logarithmic time relative to the answer space, often reducing an O(n * max_value) brute force to O(n log max_value). This technique is a staple in competitive programming and is increasingly critical in system design and backend engineering interviews.

The Optimization to Decision Reduction

The central insight is reduction: we convert an optimization problem ("what is the minimum feasible value?") into a decision problem ("is value mid feasible?"). If we can answer the decision problem in linear or polynomial time, we can binary search the answer. For example, instead of directly calculating the minimum time needed to finish all jobs with k workers, we ask: "Can all jobs be finished within T time using k workers?" This yes/no question is much simpler to implement with a greedy or simulation-based check.

When to Recognize Binary Search on Answer

You should consider binary search on answer when you see keywords like minimize the maximum, maximize the minimum, minimum feasible, smallest possible, or largest possible, coupled with constraints that are too large for brute force. Typical signals include an answer range that is bounded (e.g., between 1 and 10^9), a feasibility function that is monotonic, and a problem where checking a candidate is O(n) or O(n log n). If you can define low as the smallest impossible or trivially feasible answer and high as the largest definitely feasible answer, you likely have a candidate for this pattern.

2. How It Works

The mechanism of binary search on answer mirrors classic binary search but operates on the value domain rather than index domain. We maintain a search interval [low, high] that is guaranteed to contain the optimal answer. At each step, we compute mid = low + (high - low) // 2 to avoid overflow, and we evaluate a monotonic predicate feasible(mid). Depending on the optimization direction, we discard half of the search space. For finding the minimum feasible value, if mid is feasible, the answer lies at mid or to the left, so we set high = mid. If mid is not feasible, we must search to the right with low = mid + 1. This continues until low == high, which is the optimal value.

The predicate function is the heart of the algorithm. It must be both correct and monotonic. Monotonicity means there exists a threshold ans* such that feasible(x) == False for all x < ans* and feasible(x) == True for all x >= ans* when searching for a minimum. The inverse holds when searching for a maximum feasible value. If the predicate is not monotonic, binary search will produce incorrect results because the half-elimination logic fails. Designing this function often involves greedy simulation, counting, or checking constraints against the candidate value.

There are two canonical templates: searching for the first True (minimum feasible) and searching for the last True (maximum feasible). Choosing the correct template and loop condition is critical. The while low < high template with high = mid and low = mid + 1 is ideal for finding the lower bound and avoids infinite loops. The alternative while low <= high template requires tracking a separate answer variable and updating it when a feasible mid is found. Both are valid, but the first is less error-prone for beginners because it maintains a tight invariant that the answer is always within [low, high].

Defining the Search Space

Correctly defining low and high is essential for correctness and efficiency. low is typically the minimal possible answer — often 1, 0, the minimum element in the array, or the maximum element if the answer must be at least as large as any single item. high is the maximal possible answer — often the sum of all elements, the maximum element, or 10^9+ as per constraints. A tight bound reduces iterations, but an overly tight bound risks excluding the true answer. When in doubt, use a provably safe upper bound like 10**18 or sum(arr); the logarithmic cost means a larger range adds only a few extra iterations.

Monotonicity Proof Sketch

Before coding, you should mentally prove monotonicity. For instance, in the classic "allocate books to students to minimize the maximum pages" problem, if you can allocate books such that no student gets more than X pages, you can certainly allocate them such that no student gets more than X+1 pages — the constraint only becomes looser. This monotonic easing of constraints as the candidate value increases is what guarantees the predicate transitions from False to True exactly once. Without this proof, you risk applying binary search to a non-monotonic function and getting wrong answers on edge cases.

3. Implementation

Implementing binary search on answer cleanly requires separating concerns: the binary search driver and the feasibility checker. This separation makes code testable, reusable, and easier to debug. The driver handles bounds and mid calculation, while the checker encapsulates all problem-specific logic. Below is a robust, reusable template for finding the minimum feasible value, which is the most common variant in practice.

The template uses the low < high invariant, which guarantees termination in O(log(high - low)) steps and eliminates off-by-one errors that plague the low <= high style. Note the use of low + (high - low) // 2 instead of (low + high) // 2 to prevent integer overflow in languages like Java or C++, though in Python it is primarily a stylistic best practice. The feasibility function should be pure and efficient, ideally O(n) or O(n log n), since it will be called logarithmically many times.

def binary_search_min_feasible(low, high, feasible):
    """
    Find minimum x in [low, high] such that feasible(x) is True.
    Assumes feasible is monotonic: False...False True...True
    Returns low == high == answer, or high+1 if no feasible value.
    """
    # Invariant: answer is in [low, high], feasible(high) must be True
    while low < high:
        mid = low + (high - low) // 2
        if feasible(mid):
            # mid is feasible, answer is mid or to the left
            high = mid
        else:
            # mid is not feasible, answer must be to the right
            low = mid + 1
    return low

def binary_search_max_feasible(low, high, feasible):
    """
    Find maximum x in [low, high] such that feasible(x) is True.
    Assumes feasible is monotonic: True...True False...False
    """
    while low < high:
        # Bias mid to the right to avoid infinite loop
        mid = low + (high - low + 1) // 2
        if feasible(mid):
            low = mid  # mid feasible, try larger
        else:
            high = mid - 1  # mid not feasible, go smaller
    return low

The second template for maximum feasible requires a right-biased mid calculation. If we used the standard mid, when low + 1 == high, mid would equal low, and if feasible(mid) is True, we would set low = mid and loop forever. Adding +1 biases mid upward, ensuring progress. This subtle detail is a common source of infinite loops in interviews.

Let us ground this with a concrete, widely asked problem: Koko Eating Bananas. Koko must eat all piles of bananas within h hours, eating at speed k bananas per hour. Find the minimum integer k. The feasibility check is: can Koko finish in h hours at speed k? This is monotonic — if she can finish at speed k, she can finish at any speed > k.

from typing import List
import math

def min_eating_speed(piles: List[int], h: int) -> int:
    """
    Binary search on answer for Koko Eating Bananas.
    Search space: [1, max(piles)] or [1, max(piles)] is sufficient,
    but max(piles) is upper bound; sum(piles) also works.
    """
    def can_finish(speed: int) -> bool:
        # Total hours needed at given speed
        hours = 0
        for pile in piles:
            # ceil(pile / speed) without floating point
            hours += (pile + speed - 1) // speed
            if hours > h:  # early exit optimization
                return False
        return hours <= h

    low = 1
    high = max(piles)  # No need to go faster than largest pile
    # If h < len(piles), impossible, but constraints guarantee h >= len(piles)
    while low < high:
        mid = low + (high - low) // 2
        if can_finish(mid):
            high = mid
        else:
            low = mid + 1
    return low

# Example usage
piles = [3, 6, 7, 11]
h = 8
print(min_eating_speed(piles, h))  # Output: 4

Another classic is the Ship Within Days problem, where we binary search the ship capacity. The feasibility function greedily simulates loading packages in order and counts days needed. If days needed <= D, the capacity is feasible. This pattern of greedy simulation inside the predicate appears in over 70% of binary search on answer problems.

def ship_within_days(weights: List[int], days: int) -> int:
    """
    Find minimum ship capacity to ship all weights within 'days'.
    weights must be shipped in order, cannot split a weight.
    """
    def can_ship(capacity: int) -> bool:
        required_days = 1
        current_load = 0
        for w in weights:
            if w > capacity:
                return False  # single package exceeds capacity
            if current_load + w > capacity:
                required_days += 1
                current_load = w
                if required_days > days:
                    return False
            else:
                current_load += w
        return required_days <= days

    low = max(weights)  # at least max single weight
    high = sum(weights)  # at most sum of all weights (one day)
    while low < high:
        mid = low + (high - low) // 2
        if can_ship(mid):
            high = mid
        else:
            low = mid + 1
    return low

For maximizing problems, consider Aggressive Cows: place c cows in stalls such that minimum distance between any two cows is maximized. Here we search for the largest feasible minimum distance. The predicate checks if we can place at least c cows with at least mid distance apart using a greedy placement.

def aggressive_cows(stalls: List[int], cows: int) -> int:
    """
    Maximize minimum distance between cows.
    Search for maximum feasible distance.
    """
    stalls.sort()
    
    def can_place(min_dist: int) -> bool:
        count = 1  # place first cow at first stall
        last_pos = stalls[0]
        for i in range(1, len(stalls)):
            if stalls[i] - last_pos >= min_dist:
                count += 1
                last_pos = stalls[i]
                if count >= cows:
                    return True
        return count >= cows

    low = 0  # minimum distance could be 0
    high = stalls[-1] - stalls[0]  # max possible distance
    # Use max-feasible template
    while low < high:
        mid = low + (high - low + 1) // 2
        if can_place(mid):
            low = mid
        else:
            high = mid - 1
    return low

# Example: stalls = [1,2,8,4,9], cows=3 -> answer 3

4. Step-by-Step Example

Let us walk through a complete execution of binary search on answer using the Koko Eating Bananas example with piles = [3, 6, 7, 11] and h = 8. Our goal is to find the minimum integer speed k such that Koko can eat all piles within 8 hours. The search space is [1, 11] where 11 is max(piles). We will trace the low < high template for minimum feasible.

We define can_finish(k) as sum(ceil(pile/k) for pile in piles) <= 8. Let us compute this for several values to see monotonicity: at k=1, hours = 3+6+7+11=27 >8 False; k=2, hours=2+3+4+6=15 False; k=3, hours=1+2+3+4=10 False; k=4, hours=1+2+2+3=8 True; k=5, hours=1+2+2+3=8 True; k=11, hours=1+1+1+1=4 True. The predicate transitions from False to True at k=4 and stays True thereafter — perfect monotonicity.

Now trace the binary search. Initially low=1, high=11. Iteration 1: mid = 1 + (11-1)//2 = 6. Check can_finish(6): ceil(3/6)=1, ceil(6/6)=1, ceil(7/6)=2, ceil(11/6)=2 total=6 <=8 True, so high=6. New interval [1,6]. Iteration 2: mid = 1 + (6-1)//2 = 3. Check can_finish(3): 1+2+3+4=10 >8 False, so low=4. Interval [4,6]. Iteration 3: mid = 4 + (6-4)//2 = 5. Check can_finish(5): 1+2+2+3=8 True, so high=5. Interval [4,5]. Iteration 4: mid = 4 + (5-4)//2 = 4. Check can_finish(4): 1+2+2+3=8 True, so high=4. Now low=4, high=4 loop terminates and returns 4, which is optimal.

Visualizing the Search Space Reduction

Notice how each iteration halves the search space: 11 -> 6 -> 3 -> 2 -> 1 element. This logarithmic reduction is why binary search is so efficient even when high is 10^9 or 10^18 — it takes only about 30 to 60 iterations. The key invariant maintained is that low is always the smallest value that could still be the answer, and high is always feasible. Initially high=11 is feasible, and we never move high to an infeasible value. This invariant guarantees correctness.

Why Greedy Check Works Inside

In this example, the feasibility check is a simple summation, but in more complex problems like ship capacity or book allocation, the check itself is greedy. For ship capacity, we greedily fill the ship day by day; this greedy is optimal for the decision problem because if a capacity can work with any allocation, it can work with the greedy allocation that packs as much as possible each day. Understanding why the greedy check is correct is as important as the binary search itself — an incorrect checker will lead to wrong answers even with perfect binary search logic.

5. Complexity Analysis

The time complexity of binary search on answer is determined by two factors: the number of binary search iterations and the cost of the feasibility check. The number of iterations is O(log(high - low)), which is O(log(range)) where range is the size of the answer domain. If high can be up to 10^9, log2(10^9) is about 30. If high is up to 10^18, it is about 60. This logarithmic factor is extremely small, which is why the technique scales to huge constraints.

The feasibility check cost, denoted as O(F), depends entirely on the problem. Most checks are O(n) linear scans, O(n log n) if sorting is involved, or O(n * m) for matrix problems. The overall time complexity is therefore O(F * log(range)). For example, Koko Eating Bananas is O(n log(maxPile)), Ship Within Days is O(n log(sumWeights)), and Aggressive Cows is O(n log n + n log(range)) due to initial sorting. Space complexity is typically O(1) auxiliary besides input storage, or O(n) if the checker requires additional arrays, but the binary search itself uses constant extra space.

It is important to distinguish between best, average, and worst cases. Unlike classic binary search on a sorted array where best case is O(1) if the target is at mid, binary search on answer almost always runs for the full logarithmic iterations because we must narrow down to a single value. There is no early exit when we find a feasible mid — we must continue to verify if a smaller feasible value exists. Therefore best, average, and worst case time are essentially the same: Theta(F * log(range)). The only variation is if the feasibility check has early exit optimization, which can make infeasible checks faster on average.

R = high - low (answer range). * Early exit in checker can make best case slightly faster but asymptotically same. Note that log R is typically 30-60 for 32/64-bit integers, so the dominant factor is F. This table highlights why optimizing the feasibility function is crucial — a 2x speedup in F halves total runtime, while halving R only saves one iteration.

Comparison to Brute Force

A brute force approach would iterate through every candidate answer from low to high and check feasibility, costing O(R * F). For R = 10^9, this is infeasible. Binary search reduces this to O(F log R), an exponential improvement. For instance, if F = O(n) with n=10^5 and R=10^9, brute force is 10^14 operations (impossible), while binary search is 10^5 * 30 = 3*10^6 operations (trivial). This is the core value proposition.

6. Variations and Optimizations

Binary search on answer has several important variations beyond the basic min-feasible and max-feasible templates. One common variant is binary search on a real-valued answer, where the search space is continuous and we iterate until the interval width is below an epsilon like 1e-6 or 1e-7. This is used for problems involving minimization of maximum distance, allocation with floating point precision, or geometric problems. Instead of while low < high, we use while high - low > eps and run for a fixed 80-100 iterations to guarantee precision for double values.

Another variation is searching for the k-th feasible or using parallel binary search. In some problems, we need to find the minimal value where a counting predicate exceeds k, such as finding the k-th smallest number in a multiplication table or the k-th smallest pair distance. The predicate becomes count(x) >= k, which is still monotonic. Parallel binary search extends this to handle multiple queries simultaneously by batching feasibility checks, useful in offline queries and competitive programming.

Optimization techniques focus on tightening bounds and accelerating the checker. For bounds, we can use better initial estimates: instead of low=1, high=10^9, we might set low = max(arr) and high = sum(arr) for partition problems, which can save 10-15 iterations. For the checker, early termination is powerful — if we are counting hours and already exceed h, we can return False immediately without processing remaining elements. Memoization or prefix sums can also speed up repeated checks if the predicate involves range queries.

Integer vs. Real Number Search

When searching over integers, we must be careful with mid bias and termination. For reals, we avoid integer division issues and instead use mid = (low + high) / 2.0. The number of iterations for reals is determined by required precision: to get 1e-6 precision over range 10^9, we need about log2(10^9 / 1e-6) ≈ 50 iterations. A fixed 100 iterations is a safe universal choice that works for 1e-9 precision without needing epsilon tuning.

Using Library Functions

In Python, you can sometimes leverage bisect module ideas, but for binary search on answer you typically write the loop manually because the predicate is custom. However, understanding bisect_left and bisect_right helps internalize the lower-bound and upper-bound concepts. Some engineers also use recursive binary search, but iterative is preferred for avoiding recursion depth limits and being slightly faster. Always prefer iterative with explicit low/high variables for clarity and performance.

7. Real-World Applications

Binary search on answer is not just an interview trick; it is widely deployed in production systems where resource optimization is critical. In web servers and load balancers, it is used to find the minimum number of servers or minimum capacity needed to handle peak traffic with latency constraints. The feasibility check simulates request handling under a candidate capacity, and the monotonic property holds: if k servers can handle the load, k+1 servers certainly can. This allows auto-scaling systems to efficiently compute optimal provisioning without exhaustive search.

In databases, query optimizers use this technique to determine optimal buffer pool sizes, partition counts, or sharding thresholds. For example, finding the smallest partition size such that query latency stays below a service level agreement (SLA) involves binary searching partition sizes and checking latency via cost models or sampling. Similarly, in networking, it is used for bandwidth allocation, finding the maximum minimal bandwidth that can be guaranteed to all flows (max-min fairness), and for determining the minimal transmission power to maintain connectivity in wireless sensor networks.

Machine learning infrastructure also benefits heavily. When tuning hyperparameters like batch size or learning rate under memory constraints, or when finding the minimal model quantization level that preserves accuracy above a threshold, binary search on answer provides an efficient search strategy. The predicate — does the model achieve >= target accuracy at quantization level q — is monotonic because lower quantization (more compression) monotonically decreases accuracy. This is far more efficient than grid search over all possible levels.

This table illustrates the universality of the pattern. The key is identifying a resource or threshold that can be binary searched and a cheap way to test feasibility. In production, the feasibility check might involve running a simulation, querying metrics, or executing a cost model, but the binary search wrapper remains identical.

Case Study: Content Delivery Networks

Consider a CDN needing to determine the minimal cache size per edge node to achieve a 95% hit ratio. The hit ratio is monotonic with cache size — larger cache never hurts hit ratio. Instead of testing every possible cache size incrementally, engineers binary search cache sizes, using trace-driven simulation to check hit ratio for each candidate. With cache sizes ranging from 10GB to 10TB, binary search finds the optimum in ~40 simulations versus 1000+ with linear scanning, saving hours of simulation time.

8. Comparison with Alternatives

Binary search on answer is one of several approaches to optimization problems, and choosing the right tool depends on problem structure. The main alternatives are linear scan (brute force), greedy direct construction, dynamic programming, and ternary search. Linear scan is simple but only viable when the answer range is small (e.g., <10^4). Greedy direct construction attempts to build the optimal solution without searching, but it only works when the problem has a clear greedy choice for optimization, which is rare for min-max or max-min objectives.

Dynamic programming can solve many partition and allocation problems exactly, but often with higher complexity like O(n^2 * k) or O(n * sum), which becomes infeasible for large n or large sums. Binary search on answer with a greedy checker often achieves O(n log sum) which is dramatically faster. Ternary search is for unimodal functions (single peak/valley) where the predicate is not monotonic but convex; it is not interchangeable with binary search on answer. If your predicate is monotonic, binary search is the correct choice; if it is unimodal, ternary search applies.

Another alternative is using a heap or priority queue for simulation, such as always assigning the next job to the least loaded worker. While this can directly compute the minimal maximum load in O(n log k), it is often more complex to implement and may not generalize to constraints like contiguous partitions. Binary search on answer decouples the optimization from the assignment logic, making it easier to reason about and adapt to variations like "partitions must be contiguous" versus "any assignment allowed".

As the table shows, binary search on answer dominates when the answer range R is large and the feasibility check is cheap. It offers the best trade-off between generality, efficiency, and implementation simplicity for monotonic optimization problems. When R is small (<10^4) and F is expensive, linear scan may be simpler and fast enough. When the problem lacks monotonicity but has optimal substructure, DP is the fallback.

When Not to Use Binary Search on Answer

Do not use it if the predicate is not monotonic, if you can directly compute the answer in O(n) with a formula, or if the search space is not bounded or not ordered. Also avoid it if the feasibility check is itself NP-hard — then binary searching will not help. Always verify monotonicity with small examples and edge cases before committing to this approach.

9. Common Mistakes and Best Practices

Even experienced engineers make subtle errors when implementing binary search on answer. The most frequent mistake is incorrect bounds initialization. Setting low too high may exclude the true answer, while setting high too low may make the problem appear infeasible. For example, in the ship capacity problem, using low = 0 instead of low = max(weights) is not wrong but wastes iterations; using high = max(weights) instead of sum(weights) is wrong and will fail when days=1. Always derive bounds from problem constraints: low is the minimal value that could possibly be feasible, high is a value that is definitely feasible.

Off-by-one errors and infinite loops are the second major pitfall, especially when mixing the two templates. Using while low <= high with high = mid instead of high = mid - 1 can cause infinite loops. Similarly, forgetting to bias mid to the right in the max-feasible template causes stagnation when low + 1 == high. The safest practice is to standardize on one template — the while low < high with low = mid + 1 and high = mid for min-feasible — and use it consistently. Write the loop invariant as a comment to keep yourself honest.

A third common mistake is an incorrect or non-monotonic feasibility function. This often manifests as a greedy checker that is not actually optimal for the decision problem. For instance, checking if you can partition an array into k subarrays with sum <= mid using a greedy that takes as many elements as possible per partition is correct for contiguous partitions, but a greedy that sorts the array first would be wrong because it violates contiguity. Always test your checker independently on small brute-force cases: for all small inputs, compare your checker's result to a brute-force enumeration to ensure it is correct.

Best Practices Checklist

• Prove monotonicity first: Write down why feasible(mid) implies feasible(mid+1) before coding.
• Separate checker: Implement feasible(x) as a standalone pure function with clear early exits.
• Use tight but safe bounds: Derive low/high from max/sum/min constraints, not arbitrary constants.
• Test edge cases: Test with low==high, single element, all elements equal, and impossible cases.
• Use integer-safe mid: Prefer low + (high - low)//2 and right-biased variant for max search.
• Brute force validator: For n <= 8, write a brute force to validate your checker and binary search on random small inputs.
• Log iterations: During debugging, print low, high, mid, and feasible(mid) to visualize convergence.

Debugging Strategy

If your binary search returns a value that is off by one, check whether you need min-feasible vs max-feasible and whether your final return should be low or low - 1. If it loops infinitely, check mid bias. If it returns wrong answer on large inputs but passes small ones, your checker likely has an overflow, off-by-one, or early exit bug. Adding assertions like assert feasible(high) before the loop can catch bound errors early.

10. Interview Questions

Binary search on answer is a favorite in technical interviews at top companies because it tests both binary search fundamentals and the ability to design a monotonic predicate. Interviewers often present a problem that looks like it requires DP or greedy, but the optimal solution is binary search on answer. Recognizing the pattern quickly is key to solving it within the interview time limit. Below are common questions you should master, with hints on the predicate design.

When answering in an interview, start by stating the search space and monotonicity explicitly: "We can binary search the answer between X and Y because if value V is feasible, any value greater than V is also feasible." Then describe the feasibility check at a high level before coding. This structured communication shows the interviewer you understand the paradigm, not just memorizing solutions. Always discuss time complexity as O(F log R) and justify your bounds.

Question 1: Split Array Largest Sum (LeetCode 410)

Given an array nums and integer k, split nums into k non-empty contiguous subarrays to minimize the largest sum among subarrays. Return the minimized largest sum. This is the quintessential binary search on answer problem. Search space is [max(nums), sum(nums)]. Predicate: can we split into <=k subarrays where each subarray sum <= mid? Greedy: iterate, accumulate sum, start new subarray when adding next element would exceed mid. If subarrays needed <= k, feasible. Complexity O(n log sum). Follow-up: what if subarrays need not be contiguous? Then it becomes a different problem (load balancing with heaps).

Question 2: Koko Eating Bananas (LeetCode 875)

As detailed earlier, find minimum k to eat all piles within h hours. Interviewers use this as a warm-up. Expected to define predicate as sum(ceil(pile/k)) <= h and binary search k in [1, max(piles)]. Common pitfall: using floating point ceil instead of integer arithmetic (pile + k -1)//k. Follow-up: what if Koko can skip at most one pile? How does predicate change? This tests adaptability.

Question 3: Capacity to Ship Packages Within D Days (LeetCode 1011)

Weights must be shipped in order, find minimum capacity to ship within D days. Identical structure to split array but with days as k. Predicate: simulate days needed with capacity mid. Search space [max(weights), sum(weights)]. This question tests whether you can map a story problem to the abstract pattern. Be ready to explain why greedy simulation is optimal for the decision problem.

Question 4: Minimize Maximum Distance to Gas Station (LeetCode 774)

Given sorted gas stations positions and integer k, add k new stations to minimize the maximum distance between adjacent stations. Find the minimized maximum distance. This requires binary search on a real-valued answer. Predicate: given candidate distance D, can we achieve max distance <= D by adding <=k stations? For each gap gap = stations[i+1]-stations[i], stations needed = ceil(gap/D)-1. If total needed <=k, feasible. Search space [0, max_gap] with epsilon 1e-6. This tests floating point binary search.

Question 5: Aggressive Cows / Maximum Minimum Distance

Given stall positions and c cows, maximize the minimum distance between any two cows. This is the max-feasible variant. Search space [0, max(stalls)-min(stalls)]. Predicate: can we place at least c cows with at least D distance apart? Greedy: place first cow at first stall, then place next cow at earliest stall at least D away. If count >=c, feasible. This tests the right-biased mid template. Follow-up: what if stalls are not sorted? Emphasize sorting cost O(n log n).

Mastering these five covers 90% of interview variants. The key is not memorizing code but internalizing the pattern: identify optimization objective, define monotonic predicate, choose bounds, implement checker, and binary search. Practice writing the checker from scratch without looking at templates, and always test with the step-by-step trace method to catch off-by-one errors before submitting.