Binary Search Applications

[!NOTE] This module explores the core principles of Binary Search Applications, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Hook: The Answer Space

Binary Search isn’t just for finding “7” in a sorted array [1, 3, 5, 7, 9]. It is a universal technique for Optimization Problems.

If you have a function f(x) that is Monotonic (e.g., f(x) is true for all x > k), you can finding the boundary k using Binary Search.

Pattern: “Minimize the Maximum…” or “Maximize the Minimum…” usually screams Binary Search on Answer.

---

2. The Pattern: Search Space

Instead of searching an array indices 0 to N-1, we search the Answer Range [Low, High].

1. Define Bounds: What is the minimum possible answer? What is the maximum?
2. Check Function: Write boolean canDo(x) that checks if x works in O(N) time.
3. Binary Search:
   • mid = low + (high - low) / 2
   • If canDo(mid) works, maybe we can do better? (Move closer to optimal).
   • Else, mid is impossible.

---

3. Example: Koko Eating Bananas (LeetCode 875)

Problem: Koko wants to eat all piles within H hours. Return the minimum eating speed k.

• Monotonicity: If speed k=10 works, then k=11 definitely works. If k=5 fails, k=4 definitely fails.
• Bounds: Low = 1, High = Max(Piles).
• Check: Iterate piles, calculate hours needed: Math.ceil(pile / k). If totalHours ≤ H, return true.

This turns an Optimization problem into a Decision problem.

Interactive Banana Search

Speed (k): 1

Target Hours (H): 8

Total Hours Needed: 0

---

4. Deep Dive Strategy Lab: Binary Search Applications

Intuition Through Analogy

Think of this chapter like ranking candidates quickly. The goal is not to memorize a fixed trick, but to repeatedly answer:

1. What is the bottleneck?
2. Which constraint dominates (time, memory, latency, correctness)?
3. Which representation makes the bottleneck easier to eliminate?

Step-by-Step Code Walkthrough

Let’s look at the optimal implementation for Koko Eating Bananas:

class Solution {
  public int minEatingSpeed(int[] piles, int h) {
    int left = 1;
    int right = 1;
    for (int pile : piles) {
      right = Math.max(right, pile);
    }

    while (left < right) {
      int mid = left + (right - left) / 2;

      if (canEatInTime(piles, mid, h)) {
        right = mid; // Try to find a smaller speed
      } else {
        left = mid + 1; // Speed is too slow, must increase
      }
    }
    return left;
  }

  private boolean canEatInTime(int[] piles, int k, int h) {
    long hours = 0;
    for (int pile : piles) {
      hours += Math.ceil((double) pile / k);
    }
    return hours <= h;
  }
}

func minEatingSpeed(piles []int, h int) int {
  left, right := 1, 1
  for _, pile := range piles {
    if pile > right {
      right = pile
    }
  }

  for left < right {
    mid := left + (right - left) / 2
    if canEatInTime(piles, mid, h) {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return left
}

func canEatInTime(piles []int, k int, h int) bool {
  hours := 0
  for _, pile := range piles {
    hours += (pile + k - 1) / k // integer ceiling division
  }
  return hours <= h
}