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

1. Use low < high instead of low <= high → Ensures convergence without infinite loop
2. Always check bounds → Ensure low and high cover the full possible answer space
3. Avoid integer overflow → mid = low + (high - low)/2
4. 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

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

---

5. Problems to Practice

• LeetCode 875: Koko Eating Bananas
• LeetCode 1011: Capacity to Ship Packages Within D Days
• LeetCode 774: Minimize Max Distance to Gas Station
• LeetCode 275: H-Index II
• Binary search on “minimize/maximize” problems

---

✅ Blog 2 Summary:
We learned how to apply binary search on answers rather than array elements:

• Monotonic functions
• “Check” function pattern
• Minimize / maximize patterns
• Koko eating bananas, ship packages, minimum time tasks

---

Next in Series — Blog 3

Binary Search on Rotated & Special Arrays:

• Rotated sorted arrays with or without duplicates
• Bitonic / mountain arrays
• Pivot search patterns
• Java code with diagrams and examples

---