Identifying Problems Suitable for Binary Search

Binary search is applicable to optimization problems with these common features:

• Finding the minimum possible maximum value (or maximum possible minimum value)
• Determining the maximum or minimum value of a variable

If we denote the target value as target, it typically exhibits these properties:

• target has a well-defined range
• There exists a threshold point where values ≥ (or ≤) this threshold satisfy the problem constraints, while values < (or >) this threshold do not

The solution approach involves not directly computing the answer, but repeatedly testing candidate values within the defined range. This process narrows the search interval until it converges to the solution, a technique known as "binary search on answer."

Example: Beverage Purchase Problem

Consider this scenario: A beverage shop offers a promotion where customers receive one bottle cap per purchase, and every 5 caps can be exchanged for a new drink. If each drink costs $3 and someone wants to consume one drink daily for 60 days, what is the minimum amount they must spend?

Binary Search Solution

Let purchase_count represent the number of drinks purchased. The search space is [1, 60]. For each candidate mid value, we simulate the exchange process to determine if it yields at least 60 total drinks.

#include <iostream>
using namespace std;

const int TOTAL_DAYS = 60;
const int EXCHANGE_RATE = 5;
const int PRICE = 3;

bool is_feasible(int purchased) {
    int total_drinks = purchased;
    int caps = purchased;
    
    while (caps >= EXCHANGE_RATE) {
        int exchanged = caps / EXCHANGE_RATE;
        total_drinks += exchanged;
        caps = caps % EXCHANGE_RATE + exchanged;
    }
    
    return total_drinks >= TOTAL_DAYS;
}

int main() {
    int low = 1, high = 60;
    int answer = -1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        if (is_feasible(mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    
    cout << "Minimum purchases: " << answer << endl;
    cout << "Total cost: $" << answer * PRICE << endl;
    return 0;
}

This approach reduces the problem to O(log n) complexity compared to linear search.

Binary Search Templatse

Integer Search

Finding leftmost valid value:

while (left <= right) {
    long long mid = (left + right) / 2;
    if (is_valid(mid)) {
        result = mid;
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

Finding rightmost valid value:

while (left <= right) {
    int mid = (left + right) / 2;
    if (is_valid(mid)) {
        answer = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

Floating-Point Search

Left search with precision:

while (right - left >= EPSILON) {
    double mid = (left + right) / 2;
    if (is_valid(mid)) {
        right = mid;
    } else {
        left = mid;
    }
}

Right search with precision:

while (right - left >= EPSILON) {
    double mid = (left + right) / 2;
    if (is_valid(mid)) {
        left = mid;
    } else {
        right = mid;
    }
}

Practice Problems

Integer Search Problems

1. Cleaning Robots - Determine minimum cleaning range for robots to cover all positions
2. Group Formation - Minimize maximum height difference in groups
3. Candy Promotion - Similar to beverage problem with different exchange rates
4. Card Sets - Maximize number of complete card sets with blank cards
5. Star Counting - Find minimum time to count required star flashes
6. Long Jump - Minimize maximum distance between checkpoints
7. Stone Jumping - Maximize minimum jump distance by removing stones
8. Bottle Cap Placement - Maximize minimum distance between bottle caps
9. Wood Processing - Maximize uniform piece langth from logs
10. Tree Cutting - Maximize cutting height to obtain required wood
11. Sequence Partitioning - Minimize maximum segment sum
12. Aggressive Cows - Maximize minimum distance between cows
13. Road Sign Placement - Minimize maximum distance between signs

Floating-Point Search Problems

1. Loan Calculation - Determine monthly interest rate
2. Optimal Cattle Fence - Maximize average cattle count in fenced area
3. Square Root Approximation - Compute square root using iteration

Implementation Notes

The core challenge in binary search problems is designing an efficient is_valid() function that determines whether a candidate value satisfies problem constraints. This function often incorporates greedy algorithms or other optimization techniques. The binary search framework provides the efficient search mechanism, while the validation function encodes the problem-specific logic.