Binary Search on Answer

Concept

Instead of searching for a value in an array, binary search on the answer space itself. If you can check whether a candidate answer is feasible in O(n) or O(n log n), and the feasibility is monotonic (all values below some threshold fail, all above succeed, or vice versa), then binary search finds the optimal answer in O(n log range).

When to Use

• ▸Optimization problems: 'find the minimum/maximum value such that ...'
• ▸Problems where checking 'is answer X possible?' is easier than finding the answer directly
• ▸Factory machines, allocating resources, minimum time/cost problems
• ▸Any problem with a monotonic feasibility function

Intuition

Instead of asking 'what is the answer?', ask 'is X enough?' If you can answer yes/no efficiently, binary search over X. For example, 'what's the minimum time for machines to produce T items?' becomes 'can we produce T items in X minutes?' — just sum up items each machine makes in X minutes. If yes, try less time; if no, try more. The boundary between no and yes is the answer.

Complexity

Template Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n;
    long long t;
    cin >> n >> t;

    vector<long long> k(n);
    long long mn = 1e18;

    for(int i = 0; i < n; i++){
        cin >> k[i];
        mn = min(mn, k[i]);
    }

    long long l = 0, r = mn*t;
    while(l < r){
        long long mid = l + (r - l)/2;

        long long sum = 0;
        for(int i = 0; i < n; i++){
            sum += mid/k[i];
        }

        if(sum >= t){
            r = mid;
        }
        else{
            l = mid + 1;
        }
    }

    cout << l;
    return 0;
}

// Sample Input (Factory Machines):
// 3 7
// 3 2 5
//
// Sample Output:
// 8