Binary Search Implemantation Patterns

Two common binary search variations address different optimization scenarios:

Maximizing Minimum Value

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

bool validateMin(vector<long>& positions, long min_gap, int removals) {
    long prev = 0;
    int count = 0;
    for (int i = 1; i < positions.size(); i++) {
        if (positions[i] - prev < min_gap) count++;
        else prev = positions[i];
    }
    return count <= removals;
}

long findMaxMin(vector<long>& positions, long total_length, int removals) {
    long left = 0, right = total_length;
    while (left < right) {
        long mid = (left + right + 1) / 2;
        if (validateMin(positions, mid, removals)) left = mid;
        else right = mid - 1;
    }
    return left;
}

Minimizing Maximum Value

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

bool validateMax(vector<long>& positions, long max_gap, int removals) {
    long prev = 0;
    for (int i = 1; i < positions.size(); i++) {
        prev += (positions[i] - positions[i-1] - 1) / max_gap;
    }
    return prev <= removals;
}

long findMinMax(vector<long>& positions, long total_length, int removals) {
    long left = 0, right = total_length;
    while (left < right) {
        long mid = (left + right) / 2;
        if (validateMax(positions, mid, removals)) right = mid;
        else left = mid + 1;
    }
    return left;
}

Element Insertion Operation

void insertElement(vector<int>& arr, int index, int value) {
    if (index < arr.size()) {
        arr.insert(arr.begin() + index, value);
    }
}

Candy Distribution Optimization

Given n children with candy amounts, minimize transfers to equalzie distribution. Mathematical derivation shows the meedian of cumulative differences minimizes total operations.

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

long minimizeTransfers(vector<long>& candies) {
    long total = 0;
    for (long c : candies) total += c;
    long average = total / candies.size();
    
    vector<long> accum(candies.size(), 0);
    for (int i = 1; i < candies.size(); i++) {
        accum[i] = accum[i-1] + candies[i-1] - average;
    }
    
    sort(accum.begin(), accum.end());
    long median = accum[accum.size() / 2];
    long operations = 0;
    for (long val : accum) {
        operations += abs(median - val);
    }
    return operations;
}