Overview & Concept

Binary Search on Answer solves optimization problems by binary searching over the domain of possible answers [low, high] rather than search array elements. It relies on a monotonic predicate isFeasible(x) where if x is feasible, all values greater (or lesser) than x are also feasible.

How It Works

Monotonic Predicate: Identifies a decision function isFeasible(capacity) that is strictly monotonic.

Domain Identification: Defines lower bound low (min possible answer) and upper bound high (max possible answer).

Midpoint Evaluation: Computes mid and evaluates predicate in polynomial time (typically O(n)).

Search Space Halving: Shrinks domain to [low..mid-1] or [mid+1..high] based on predicate outcome.

Step-by-Step Execution

1. Bound Answer RangeSet low = max(arr) and high = sum(arr).

2. Compute Mid CandidateCalculate mid = Math.floor((low + high) / 2).

3. Verify FeasibilitySimulate allocation: count partitions needed with max capacity mid.

4. Update DomainIf feasible, record best answer = mid and test lower half high = mid - 1. Else low = mid + 1.

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(n)	O(n · log(range))	O(n · log(range))	O(1)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

procedure binarySearchOnAnswer(weights, K):
  low = max(weights), high = sum(weights)
  optimal = high
  while low <= high:
    mid = floor((low + high) / 2)
    if isFeasible(weights, mid, K):
      optimal = mid
      high = mid - 1 // try smaller capacity
    else:
      low = mid + 1 // capacity too small
  return optimal

Algorithmic Invariants

Monotonicity Invariant: For all x >= optimal, isFeasible(x) is true; for all x < optimal, isFeasible(x) is false.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Turns complex NP-hard looking minimax optimization problems into straightforward O(n log(range)) algorithms.
•Guaranteed convergence to the globally optimal threshold.

Trade-offs & Limitations

•Requires problem to exhibit strict monotonicity with respect to the predicate.

Real-World Applications

Resource & Capacity Planning

Finding minimum truck capacity to ship packages across D days (LeetCode 1011).

Painter Partition & Book Allocation

Equitably distributing workload across K workers to minimize peak time.

Decision Guide: When to Use

Ideal Scenarios

✓When asked to find the minimum possible maximum, or maximum possible minimum value.

Consider Alternatives When

✕When the feasibility predicate is non-monotonic or exhibits local oscillations.

Compare trade-offs and complexity across complementary tools in AlgoViz.

Binary Search Ternary Search