Search on Answer

How It Works

Binary search on the answer flips the technique inside out: rather than searching an array, you search the space of possible answers. It applies when feasibility is monotonic — if capacity C works, every capacity above C works too. Define check(x), a predicate testing whether candidate answer x is achievable, then binary search for the boundary where check flips from false to true.

Each probe costs one feasibility check, usually an O(n) greedy simulation, so the total is O(n log R) where R is the answer range. That converts optimization problems with enormous search spaces — minimum ship capacity, minimum eating speed, maximum minimum distance — into a handful of yes/no simulations instead of trying every candidate.

Step-by-Step Visualization

Code

static int minEatingSpeed(int[] piles, int h) {
  int left = 1;
  int right = 0;
  for (int p : piles) right = Math.max(right, p);

  while (left < right) {
    int mid = left + (right - left) / 2;
    int hours = 0;
    for (int p : piles) hours += (p + mid - 1) / mid;
    if (hours <= h) right = mid;
    else left = mid + 1;
  }

  return left;
}

// Example: minEatingSpeed(new int[]{3,6,7,11}, 8) → 4

Tips & Gotchas

Practice Problems

• 1Koko Eating Bananas
• 2Capacity To Ship Packages Within D Days
• 3Split Array Largest Sum
• 4Minimum Number of Days to Make m Bouquets
• 5Aggressive Cows

About the Binary Search Pattern

If the search space is sorted (or has a monotonic property), you can eliminate half of it with each comparison. This reduces O(n) linear search to O(log n). Works on arrays, answer spaces, and even abstract conditions.

Common Array Interview Problems

• Two Sum
• Best Time to Buy & Sell Stock
• Maximum Subarray
• Merge Intervals
• Product of Array Except Self
• Container With Most Water

Frequently Asked Questions

Other Binary Search Techniques