WHEN to use:

• Need to minimize / maximize a value
• Brute force over answer is possible
• Condition is monotonic (TTTTFFFF or FFFFTTTT)

⚙️ Core Idea:

Search on the answer space, not the array → use a check function (isPossible)

Template:

int l = low, r = high;
int ans = -1;

while (l <= r) {
    int mid = l + (r - l) / 2;

    if (isPossible(mid)) {
        ans = mid;        // store answer
        r = mid - 1;      // try smaller (for min)
    } else {
        l = mid + 1;
    }
}

Common Problem Examples:

1. Aggressive Cows🐄

Given an array nums of size n, which denotes the positions of stalls, and an integer k, which denotes the number of aggressive cows, assign stalls to k cows such that the minimum distance between any two cows is the maximum possible. Find the maximum possible minimum distance.

bool canPlace(vector<int> &nums,int dist,int cows){
        int placedCows=1,lastPlaced = nums[0];
        for(int stall: nums){
            if(stall==lastPlaced) continue;
            if(stall-lastPlaced>=dist){
                placedCows++;
                lastPlaced=stall;
            }
        }
        return placedCows>=cows;
    }
    int aggressiveCows(vector<int> &nums, int k) {
        sort(nums.begin(),nums.end());
        int low=1,high = nums[nums.size()-1]-nums[0];
        
        while(low<=high){
            int mid = (low+high)/2;
            if(canPlace(nums,mid,k)) low=mid+1;
            else high=mid-1;
        }
        return high;
    }

2. Koko Eating Bananas🍌

A monkey is given n piles of bananas, where the 'ith' pile has nums[i] bananas. An integer h represents the total time in hours to eat all the bananas. Each hour, the monkey chooses a non-empty pile of bananas and eats k bananas. If the pile contains fewer than k bananas, the monkey eats all the bananas in that pile and does not consume any more bananas in that hour. Determine the minimum number of bananas the monkey must eat per hour to finish all the bananas within h hours.

bool canEat(vector<int> &nums, int hrs, int &h)
    {
        long long tot = 0;
        for (int i : nums)
        {
            tot += ceil((long long)i / (double)hrs);
        }
        return tot <= h;
    }

    int minimumRateToEatBananas(vector<int> nums, int h)
    {
        int end = *max_element(nums.begin(), nums.end());
        int low = 1, high = end;
        while (low <= high)
        {
            long long mid = (low + high) / 2;
            if (canEat(nums, mid, h))
            {
                high = mid - 1;
            }
            else
            {
                low = mid + 1;
            }
        }
        return low;
    }