17. Binary Search for the Largest Batch Size Under a Latency Budget

Problem

A lab's inference serving team is tuning the batch size used to group concurrent requests on a GPU. Larger batches use the GPU more efficiently (higher throughput per dollar), but they also increase per-request p99 latency, since a request has to wait for the whole batch to finish. Given measured p99 latency for each candidate batch size (latency is non-decreasing as batch size grows, since bigger batches always do at least as much work per step), find the largest batch size whose latency still meets an SLA — without measuring every single batch size, since each measurement in production means an actual load test.

Source: src/17_binary_search_max_batch_size.py

def max_batch_size_under_latency(latencies: list[float], max_latency: float) -> int:

>>> max_batch_size_under_latency([10, 15, 22, 40, 90], 30)
3
>>> max_batch_size_under_latency([10, 15, 22, 40, 90], 5)
0

Step-by-Step Approach

1. Notice that "is batch size b feasible" (i.e. latencies[b-1] <= max_latency) is a monotonic predicate: it's True for a run of small batch sizes, then flips to False forever once latency crosses the budget, since latencies is non-decreasing. That's the precondition for binary search on the answer.
2. Set up the search range over candidate batch sizes themselves, lo = 1 to hi = len(latencies), rather than over array positions with some other meaning.
3. At each step probe the midpoint mid: check latencies[mid - 1] <= max_latency.
4. If feasible, mid is a valid answer but maybe not the largest one — record it as the current best and search the upper half (lo = mid + 1) for something even bigger.
5. If infeasible, mid and everything larger is guaranteed infeasible too (monotonicity) — discard the upper half entirely (hi = mid - 1).
6. Continue until lo > hi; the last recorded best is the largest feasible batch size, or 0 if nothing was ever feasible (including the empty-list case, where the loop body never runs).

The key insight is that this isn't "binary search for a value in a sorted array" — it's "binary search over a range of candidate answers, using a monotonic feasibility check as the comparison," which turns an O(n) measurement scan into O(log n) probes, exactly the win that matters when each probe is an expensive real-world load test rather than a free array lookup.

Reference solution

def max_batch_size_under_latency(latencies: list[float], max_latency: float) -> int:
    # binary search on the answer: latencies is monotonic non-decreasing, so
    # "is batch size b feasible" is a step function (True...True, False...
    # False) -- we're hunting the last True. O(log n) probes vs. O(n) scan.
    lo, hi = 1, len(latencies)
    best = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if latencies[mid - 1] <= max_latency:
            # batch size mid works -- it might not be the largest, keep it
            # and search the upper half for something even bigger
            best = mid
            lo = mid + 1
        else:
            # too slow at this batch size, no point trying anything bigger
            hi = mid - 1
    return best

Key Functions & Tricks

• lo, hi = 1, len(latencies) — the search range is over batch sizes (the answer space), not array indices directly.
• mid = (lo + hi) // 2 — standard midpoint probe; each iteration halves the remaining candidate range.
• best = mid; lo = mid + 1 — records a feasible answer before continuing to search for a possibly-larger one, instead of stopping at the first hit.
• hi = mid - 1 — prunes the entire upper half once infeasibility is confirmed, relying on monotonicity rather than checking each value individually.
• best initialized to 0 — doubles as the correct answer for both "nothing is feasible" and "the list is empty," with no separate edge-case branch needed.

How to Recognize This Pattern