Binary Search on Answer

Key Signals & Indicators

• Target variable is bounded (e.g. min possible output to max possible output)
• Feasible check is monotonic (if X is feasible, then X+1 is feasible, etc.)
• Finding an optimized min/max value under constraints

// C++ Binary Search on Answer Template
#include <vector>

bool isValid(const std::vector<int>& arr, int mid, int constraint);

int searchOnAnswer(const std::vector<int>& arr, int constraint) {
    int low = 1; // Minimum possible answer
    int high = 1e9; // Maximum possible answer
    int ans = -1;
    
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (isValid(arr, mid, constraint)) {
            ans = mid; // Candidate solution found
            high = mid - 1; // Try to find a smaller feasible answer
        } else {
            low = mid + 1; // Mid is too small, increase target space
        }
    }
    return ans;
}