Binary search doesn’t require an array at all. Any time a problem asks you to minimize the maximum (or maximize the minimum) of something, and “can we achieve X?” gets easier to answer as X grows, you can binary search directly over the space of possible answers — no array indices in sight.

What you’ll learn

• How to recognize the cue: “minimize the maximum” / “maximize the minimum”, with a feasibility check that gets monotonically easier or harder.
• The reusable template: binary search over [lo, hi][lo, hi] guided by a feasible(mid)feasible(mid) predicate, instead of arr[mid]arr[mid].
• Three worked shapes of the same pattern: Capacity To Ship Packages Within D Days, Koko Eating Bananas, and Split Array Largest Sum.
• Why it costs $O(n \log(\text{range}))$, and the one design step that makes or breaks it: proving your predicate is actually monotonic.

The cue: minimize the maximum, maximize the minimum

Look for a hidden number line of candidate answers where one side is always “too small/slow/tight” and the other side is always “big/generous enough” — with a clean cutoff in between. That cutoff is your answer, and a feasible(candidate)feasible(candidate) function tells you which side of it you’re on.

Capacity To Ship Packages Within D Days: a conveyor belt ships weightsweights in order, loading as many consecutive packages as fit under a daily capacitycapacity before starting a new day. Find the minimum capacitycapacity that ships everything within daysdays days.

As capacitycapacity grows, the number of days needed only ever decreases (or stays the same) — never increases. That monotonic relationship is exactly what binary search needs, even though there’s no array of “capacities” to search — just the range of integers from the largest single package up to the sum of everything.

The pattern: binary search over a feasibility predicate

def ship_within_days(weights, days):
    def days_needed(capacity):
        # Greedily pack today's shipment; start a new day when the next
        # package would overflow the current one.
        days_used = 1
        current_load = 0
        for w in weights:
            if current_load + w > capacity:
                days_used += 1
                current_load = 0
            current_load += w
        return days_used
 
    lo, hi = max(weights), sum(weights)   # answer must be in [largest single package, ship it all in one day]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if days_needed(mid) <= days:
            hi = mid          # capacity=mid WORKS -- try a smaller (tighter) capacity
        else:
            lo = mid + 1      # capacity=mid too small -- need more room per day
    return lo
 
 
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(ship_within_days(weights, 5))   # expect 15

def ship_within_days(weights, days):
    def days_needed(capacity):
        # Greedily pack today's shipment; start a new day when the next
        # package would overflow the current one.
        days_used = 1
        current_load = 0
        for w in weights:
            if current_load + w > capacity:
                days_used += 1
                current_load = 0
            current_load += w
        return days_used
 
    lo, hi = max(weights), sum(weights)   # answer must be in [largest single package, ship it all in one day]
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if days_needed(mid) <= days:
            hi = mid          # capacity=mid WORKS -- try a smaller (tighter) capacity
        else:
            lo = mid + 1      # capacity=mid too small -- need more room per day
    return lo
 
 
weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(ship_within_days(weights, 5))   # expect 15

The shape never changes: pick bounds you’re certain bracket the answer, write a feasible(mid)feasible(mid) check, and narrow with lo < hilo < hi exactly like the lower_boundlower_bound template — except midmid is a candidate answer, not an array index.

How it works

Worked example: Koko Eating Bananas

Same shape, different feasibility check. Koko eats at most speedspeed bananas per pile per hour; find the minimum speedspeed that finishes every pile within hh hours.

import math
 
def min_eating_speed(piles, h):
    def hours_needed(speed):
        return sum(math.ceil(pile / speed) for pile in piles)
 
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours_needed(mid) <= h:
            hi = mid          # speed=mid is fast enough -- try slower
        else:
            lo = mid + 1      # speed=mid too slow -- need faster
    return lo
 
 
print(min_eating_speed([3, 6, 7, 11], 8))   # expect 4

import math
 
def min_eating_speed(piles, h):
    def hours_needed(speed):
        return sum(math.ceil(pile / speed) for pile in piles)
 
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours_needed(mid) <= h:
            hi = mid          # speed=mid is fast enough -- try slower
        else:
            lo = mid + 1      # speed=mid too slow -- need faster
    return lo
 
 
print(min_eating_speed([3, 6, 7, 11], 8))   # expect 4

And Split Array Largest Sum — split numsnums into mm contiguous subarrays, minimizing the largest subarray sum — reuses the exact greedy feasibility check from the shipping problem, just renamed:

def split_array_largest_sum(nums, m):
    def pieces_needed(max_sum):
        pieces = 1
        current_sum = 0
        for x in nums:
            if current_sum + x > max_sum:
                pieces += 1
                current_sum = 0
            current_sum += x
        return pieces
 
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if pieces_needed(mid) <= m:
            hi = mid
        else:
            lo = mid + 1
    return lo
 
 
print(split_array_largest_sum([7, 2, 5, 10, 8], 2))   # expect 18

def split_array_largest_sum(nums, m):
    def pieces_needed(max_sum):
        pieces = 1
        current_sum = 0
        for x in nums:
            if current_sum + x > max_sum:
                pieces += 1
                current_sum = 0
            current_sum += x
        return pieces
 
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if pieces_needed(mid) <= m:
            hi = mid
        else:
            lo = mid + 1
    return lo
 
 
print(split_array_largest_sum([7, 2, 5, 10, 8], 2))   # expect 18

Three different problem statements, the same eleven lines of binary search scaffolding, and only the feasiblefeasible/hours_neededhours_needed/pieces_neededpieces_needed helper changes.

Time and space complexity

rangerange is hi - lohi - lo in your chosen bounds — for Koko it’s max(piles)max(piles), for shipping/splitting it’s sum(nums) - max(nums)sum(nums) - max(nums).

When to use it

• The problem asks to minimize a maximum or maximize a minimum (capacity, speed, largest chunk, smallest gap) subject to a constraint.
• You can write a feasible(candidate)feasible(candidate) check, typically a single greedy $O(n)$ pass, and you can argue it’s monotonic in candidatecandidate.
• The “search space” of candidate answers is large enough that trying every value would be too slow, but bounded enough to pick honest lolo/hihi.
• Classic tell for “maximize the minimum spacing” variants (aggressive cows / minimize max distance between chosen points): the predicate becomes “can we place everything with at least this much spacing?”, and larger spacing only ever gets harder to satisfy.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 875 — Koko Eating Bananas · Medium

Problem. Koko eats at a speed of kk bananas per hour, taking a whole hour per pile even if the pile has fewer than kk left. Return the minimum kk that lets her finish all piles within hh hours.

Constraints. 1 <= len(piles) <= 10^41 <= len(piles) <= 10^4, piles.length <= h <= 10^9piles.length <= h <= 10^9, 1 <= piles[i] <= 10^91 <= piles[i] <= 10^9.

Examples. piles = [3,6,7,11], h = 8piles = [3,6,7,11], h = 8 gives 44 · piles = [30,11,23,4,20], h = 5piles = [30,11,23,4,20], h = 5 gives 3030 · h = 6h = 6 gives 2323

LC 1011 — Capacity To Ship Packages Within D Days · Medium

Problem. Packages must be shipped in order within daysdays days. Return the minimum ship capacity that makes this possible.

Constraints. 1 <= days <= len(weights) <= 5 * 10^41 <= days <= len(weights) <= 5 * 10^4, 1 <= weights[i] <= 5001 <= weights[i] <= 500.

Examples. weights = [1,2,3,4,5,6,7,8,9,10], days = 5weights = [1,2,3,4,5,6,7,8,9,10], days = 5 gives 1515 · weights = [3,2,2,4,1,4], days = 3weights = [3,2,2,4,1,4], days = 3 gives 66 · weights = [1,2,3,1,1], days = 4weights = [1,2,3,1,1], days = 4 gives 33

LC 410 — Split Array Largest Sum · Hard

Problem. Split numsnums into kk non-empty contiguous subarrays, minimising the largest subarray sum. Return that minimum.

Constraints. 1 <= len(nums) <= 10001 <= len(nums) <= 1000, 0 <= nums[i] <= 10^60 <= nums[i] <= 10^6, 1 <= k <= min(50, len(nums))1 <= k <= min(50, len(nums)).

Examples. nums = [7,2,5,10,8], k = 2nums = [7,2,5,10,8], k = 2 gives 1818 · nums = [1,2,3,4,5], k = 2nums = [1,2,3,4,5], k = 2 gives 99 · nums = [1,4,4], k = 3nums = [1,4,4], k = 3 gives 44

LeetCode problem set

Recap

• The cue is “minimize the maximum” / “maximize the minimum” with a feasibility check that only gets easier (or only harder) as the candidate answer grows.
• The template is always the same eleven-ish lines: honest lolo/hihi bounds, while lo < hiwhile lo < hi, feasible(mid)feasible(mid) decides hi = midhi = mid or lo = mid + 1lo = mid + 1.
• Cost is $O(n \log(\text{range}))$ — one $O(n)$ feasibility pass per binary search step.
• The one thing that can silently break this pattern: a feasibility check that isn’t actually monotonic. Prove monotonicity in words before you trust the binary search around it.

Next: Monotonic Stack — maintaining an increasing or decreasing stack to answer “next greater/smaller” questions in a single pass.