Binary Search Patterns Series — Blog 2: Monotonic Functions & Answer Search

1. Concept

Unlike classic binary search on arrays, here we are searching for an “answer”. We have:

A monotonic function f(x) (either increasing or decreasing)
A condition we want to satisfy, e.g., f(x) >= target
We want the minimum or maximum x satisfying the condition

Template:

long low = 0, high = 1_000_000_000; // search space
while (low < high) { // note: strict < for answer search
    long mid = low + (high - low) / 2;
    if (check(mid)) high = mid; // condition satisfied, try smaller
    else low = mid + 1;          // condition not satisfied, increase
}
return low; // smallest x satisfying condition

2. Key Tips for Answer Search

Use low < high instead of low <= high → Ensures convergence without infinite loop
Always check bounds → Ensure low and high cover the full possible answer space
Avoid integer overflow → mid = low + (high - low)/2
Define a check(mid) function → Returns true if condition satisfied

3. Classic Examples

3.1 Koko Eating Bananas

Problem:
Koko can eat k bananas per hour. Given piles and h hours, find minimum k to finish all bananas.

public int minEatingSpeed(int[] piles, int h) {
    int low = 1, high = Arrays.stream(piles).max().getAsInt();

    while (low < high) {
        int mid = low + (high - low) / 2;
        if (canFinish(piles, mid, h)) high = mid; // possible, try smaller
        else low = mid + 1;                        // not enough, increase
    }
    return low;
}

private boolean canFinish(int[] piles, int k, int h) {
    int hours = 0;
    for (int pile : piles) {
        hours += (pile + k - 1) / k; // ceiling division
    }
    return hours <= h;
}

3.2 Capacity to Ship Packages Within D Days

public int shipWithinDays(int[] weights, int D) {
    int low = Arrays.stream(weights).max().getAsInt();
    int high = Arrays.stream(weights).sum();

    while (low < high) {
        int mid = low + (high - low)/2;
        if (canShip(weights, D, mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

private boolean canShip(int[] weights, int D, int cap) {
    int days = 1, current = 0;
    for (int w : weights) {
        if (current + w > cap) {
            days++;
            current = 0;
        }
        current += w;
    }
    return days <= D;
}

3.3 Minimum Time to Complete Tasks

Problem: You have n workers, each worker takes time[i] per task. Find the minimum time to complete totalTasks.

public long minTime(int[] time, long totalTasks) {
    long low = 1, high = (long)1e18;
    while (low < high) {
        long mid = low + (high - low)/2;
        if (canComplete(time, totalTasks, mid)) high = mid;
        else low = mid + 1;
    }
    return low;
}

private boolean canComplete(int[] time, long totalTasks, long t) {
    long count = 0;
    for (int i : time) {
        count += t / i;
        if (count >= totalTasks) return true;
    }
    return count >= totalTasks;
}

4. Edge Cases

Single-element arrays → check if your low and high cover all possibilities
Very large numbers → always use long for sum/multiplication
Strict inequality → choose < or <= carefully in while loop
Ceiling division → (x + y - 1)/y for integer math