Binary search is an efficient algorithm for locating a target value within a sorted sequence. Its core principle involves repeatedly dividing the search interval in half, leveraging monotonic properties to eliminate large portions of the search space without explicit enumeration.

Implementation Strategy

1. Identify Monotonicity: Analyze the problem to confirm that a function exists where the validity of a candidate answer changes predictably (e.g., from 'feasible' to 'infeasible') as the value increases or decreases.
2. Define Search Boundaries: Establish the initial search interval [low, high]. The boundaries must guarantee that the optimal answer lies within this range. Common practice is to set low to a value known to be invalid and high to a value known to be valid, or vice versa, depending on the search target.
3. Design Validation Function: Implement a bool feasible(int candidate) function. This function determines whether a given candidate value satisfies the problem's constraints or represents a potential solution.
4. Iterative Narrowing: Calculate the midpoint mid = low + (high - low) / 2. Evaluate feasible(mid) to decide which half of the interval to discard, updating low or high accordingly. The loop continues until the interval is sufficiently small.

Binary Search for Optimization

This technique is widely used for optimization problems where you seek a maximum or minimum value subject to constraints. The process involves searching through the space of possible answers using binary search, with the feasible function acting as a guide.

General Patttern:

bool feasible(int candidate) {
    // Determine if 'candidate' meets the required conditions.
    // Return true if it's a viable solution, false otherwise.
}

int findOptimalValue() {
    int low = MIN_VALID;   // Lower bound of search space
    int high = MAX_VALID;  // Upper bound of search space

    while (low < high) {
        // For finding the maximum feasible value
        int mid = low + (high - low + 1) / 2;
        if (feasible(mid)) {
            low = mid; // Candidate is feasible, try larger values
        } else {
            high = mid - 1; // Candidate is infeasible, must decrease
        }
        // For finding the minimum feasible value, the update logic is inverted.
    }
    return low; // or high, as they converge
}

Example 1: Maximizing Minimum Distance

This problem involves placing points along a line to maximize the smallest distance between any two points after potentially removing some.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canAchieveDistance(const vector<int>& positions, int minDist, int maxRemovals) {
    int removalsUsed = 0;
    int lastKeptPos = positions[0];

    for (int i = 1; i < positions.size(); ++i) {
        if (positions[i] - lastKeptPos < minDist) {
            removalsUsed++; // Remove this point
            if (removalsUsed > maxRemovals) return false;
        } else {
            lastKeptPos = positions[i]; // Keep this point
        }
    }
    return true;
}

int maxMinDistance(vector<int>& positions, int totalLength, int maxRemovals) {
    sort(positions.begin(), positions.end());
    int low = 1; // Minimum possible distance
    int high = totalLength; // Maximum possible distance

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canAchieveDistance(positions, mid, maxRemovals)) {
            low = mid + 1; // Try for a larger minimum distance
        } else {
            high = mid - 1; // Distance is too large, reduce it
        }
    }
    return high; // 'high' holds the maximum achievable minimum distance
}

int main() {
    int length = 25, maxRemovals = 3;
    vector<int> rocks = {2, 8, 11, 15, 20};
    cout << maxMinDistance(rocks, length, maxRemovals) << endl; // Output: 5
    return 0;
}

Example 2: Determining Maximum Bouquet Count

Given counts of different flower types and a required number of flowers per bouquet, find the maximum number of complete bouquets that can be formed.

#include <iostream>
#include <vector>
using namespace std;

bool canMakeBouquets(const vector<long long>& flowerCounts, long long bouquetSize, long long targetBouquetCount) {
    long long totalFlowersAvailable = 0;
    for (long long count : flowerCounts) {
        // From each type, we can contribute at most 'bouquetSize' flowers
        // or all available flowers if less than 'bouquetSize'.
        totalFlowersAvailable += min(count, bouquetSize);
    }
    // Check if total flowers are enough for the target number of bouquets.
    return (totalFlowersAvailable / bouquetSize) >= targetBouquetCount;
}

long long maxPossibleBouquets(vector<long long>& flowerCounts, long long bouquetSize) {
    long long totalFlowers = 0;
    for (long long count : flowerCounts) totalFlowers += count;
    long long low = 0;
    long long high = totalFlowers / bouquetSize; // Theoretical maximum

    while (low < high) {
        // Use upper mid to avoid infinite loop
        long long mid = low + (high - low + 1) / 2;
        if (canMakeBouquets(flowerCounts, bouquetSize, mid)) {
            low = mid; // 'mid' bouquets are possible, try for more
        } else {
            high = mid - 1; // 'mid' is not possible, reduce target
        }
    }
    return low;
}

int main() {
    vector<long long> flowers = {5, 4, 3, 8, 10};
    long long k = 3; // Flowers per bouquet
    cout << maxPossibleBouquets(flowers, k) << endl; // Output: 7
    return 0;
}