Binary Search on Answer

Binary search on answer is a powerful technique for solving optimization problems where we binary search on the answer space rather than the array.

When to Use

Use binary search on answer when:

1. You need to find minimum/maximum value satisfying a condition
2. The answer space is monotonic - if value x works, all values > x (or < x) also work
3. You can efficiently check feasibility for a given value

The Pattern

// Template for binary search on answer
public int binarySearchOnAnswer(int[] arr) {
    int low = minValue;  // Minimum possible answer
    int high = maxValue; // Maximum possible answer
    
    while (low < high) {
        int mid = low + (high - low) / 2;
        
        if (isFeasible(arr, mid)) {
            high = mid;  // Try to find smaller answer
        } else {
            low = mid + 1;  // Need larger answer
        }
    }
    
    return low;  // Minimum feasible answer
}

// Check if mid is a valid answer
boolean isFeasible(int[] arr, int value) {
    // Check if 'value' satisfies the constraint
    // Return true if feasible, false otherwise
}

Example: Minimum Capacity to Ship Packages

// Problem: Ship packages within D days with minimum capacity
// Binary search on capacity (answer)

public int shipWithinDays(int[] weights, int days) {
    int low = 0;  // Minimum capacity: max weight
    int high = 0; // Maximum capacity: sum of all weights
    
    for (int w : weights) {
        low = Math.max(low, w);
        high += w;
    }
    
    while (low < high) {
        int mid = low + (high - low) / 2;
        
        if (canShipWithinDays(weights, days, mid)) {
            high = mid;  // Try smaller capacity
        } else {
            low = mid + 1;  // Need larger capacity
        }
    }
    
    return low;
}

boolean canShipWithinDays(int[] weights, int days, int capacity) {
    int currentLoad = 0;
    int daysNeeded = 1;
    
    for (int w : weights) {
        if (currentLoad + w > capacity) {
            daysNeeded++;
            currentLoad = 0;
        }
        currentLoad += w;
    }
    
    return daysNeeded <= days;
}

Complexity Analysis

• Time: O(n × log(sum - max)) where n is array length
• Space: O(1)

The binary search runs in O(log(sum - max)) iterations, each requiring O(n) feasibility check.

The key to binary search on answer is designing an efficient feasibility function that checks if a given value works.

Common Feasibility Patterns

1. Greedy Check

// Check if we can split array into k parts with max sum <= target
boolean canSplit(int[] nums, int k, int target) {
    int count = 1;
    int currentSum = 0;
    
    for (int num : nums) {
        if (currentSum + num > target) {
            count++;
            currentSum = num;
            if (count > k) return false;
        } else {
            currentSum += num;
        }
    }
    return true;
}

2. Counting Check

// Check if we can place m balls with minimum distance >= target
boolean canPlace(int[] positions, int m, int target) {
    int count = 1;
    int lastPosition = positions[0];
    
    for (int i = 1; i < positions.length; i++) {
        if (positions[i] - lastPosition >= target) {
            count++;
            lastPosition = positions[i];
            if (count >= m) return true;
        }
    }
    return false;
}

3. Binary Search within Feasibility Check

// Check if median is <= target
boolean isMedianBelowTarget(int[] nums, int target) {
    int countLess = 0;
    for (int num : nums) {
        if (num <= target) countLess++;
    }
    return countLess > nums.length / 2;
}

Example: Magnetic Force Between Balls

public int maxDistance(int[] position, int m) {
    Arrays.sort(position);
    
    int low = 1;
    int high = position[position.length - 1] - position[0];
    
    while (low < high) {
        int mid = low + (high - low + 1) / 2;  // Ceil division
        
        if (canPlaceBalls(position, m, mid)) {
            low = mid;  // Try larger distance
        } else {
            high = mid - 1;  // Need smaller distance
        }
    }
    
    return low;
}

boolean canPlaceBalls(int[] position, int m, int minForce) {
    int count = 1;
    int lastPos = position[0];
    
    for (int i = 1; i < position.length; i++) {
        if (position[i] - lastPos >= minForce) {
            count++;
            lastPos = position[i];
            if (count >= m) return true;
        }
    }
    return false;
}

Tips for Designing Feasibility Functions

1. Greedy approach: Usually O(n) time
2. Monotonic property: If value x works, all values > x (or < x) also work
3. Clear boundary: Define what "works" means clearly
4. Edge cases: Handle empty input, single element

Common Binary Search on Answer Problems

Problem	Answer Space	Feasibility Check
Ship packages	Capacity	Greedy simulation
Split array	Maximum sum	Greedy counting
Magnetic force	Distance	Greedy placement
Koko eating bananas	Eating speed	Time calculation