Binary Search Patterns

🎯 The Binary Search on the Answer Pattern

This guide provides a structured template and plug-in snippets for solving competitive programming problems that ask for the minimum or maximum value satisfying a condition (e.g., minimum speed, maximum capacity). This pattern is known as Binary Search on the Answer.

🧠 When to Use This Pattern

Use this template when:

1. The Answer is Unknown: The problem asks for the minimum possible X or maximum possible X (e.g., speed, time, rate).
2. The Search Space is Large: The range of possible answers for X is too large for a simple loop (e.g., up to $10^9$ or $10^{14}$).
3. The Check is Monotonic: The feasibility of a solution is monotonic. That is, if a value $\text{mid}$ works, all values “better” (smaller/larger, depending on the goal) than $\text{mid}$ might also work, and all values “worse” definitely fail. This allows the search space to be cut in half repeatedly.

---

🛠️ The Core Python Template (Minimization Focus)

The structure below is optimized for finding the Minimum valid integer answer, which is the most common use case.

import math
from typing import List, Tuple, Any
 
class Solution:
    
    # ----------------------------------------------------------------------
    # 1. PLUG-IN: The Feasibility Check Function (CHECK_SNIPPET_A)
    # ----------------------------------------------------------------------
    def check(self, mid: int, *inputs: Any) -> bool:
        """
        Calculates the required effort/result for the candidate answer 'mid'.
        Returns True if 'mid' is a valid solution (e.g., meets the deadline).
        """
        # ⚠️ Replace this with the logic specific to your problem ⚠️
        
        # Example: Koko Eating Bananas
        piles, H = inputs
        if mid == 0: return False
        
        hours_spent = 0
        for pile in piles:
            hours_spent += math.ceil(pile / mid)
            
        return hours_spent <= H
        
    # ----------------------------------------------------------------------
    
    def solve(self, *inputs: Any) -> int:
        
        # ----------------------------------------------------------------------
        # 2. PLUG-IN: Define the Search Bounds (BOUNDS_SNIPPET_B)
        # ----------------------------------------------------------------------
        # Find the smallest and largest possible valid answers for the problem.
        # Example: Koko Eating Bananas (piles, H)
        piles = inputs[0] # Assuming piles is the first input
        left = 1 
        right = max(piles) 
        # ----------------------------------------------------------------------
        
        optimal_answer = -1
        
        while left <= right:
            mid = left + (right - left) // 2
            
            # Check feasibility using the plugged-in function
            if self.check(mid, *inputs):
                # SUCCESS: 'mid' is valid.
                # Store it as a potential answer.
                optimal_answer = mid
                
                # Since we are minimizing, try to find a *smaller* (better) answer.
                right = mid - 1
            else:
                # FAILURE: 'mid' is NOT valid (too small/slow).
                # Must try a *larger* (worse/faster) answer.
                left = mid + 1
                
        return optimal_answer

---

🔌 Problem-Specific Plug-In Snippets

Use these snippets to replace the placeholders in the template. Remember to adjust the function signature of solve and the unpacking of *inputs as needed.

🧩 Snippet A: The Feasibility Check

Problem	Goal	Logic to Implement in check(mid, *inputs)
Minimum Speed to Arrive (dist, hour)	Find $\min (\text{speed})$ such that $\text{time}\le \text{hour}$	Calculate $T={\sum }_{i=0}^{n-2}\lceil \frac{d_i}{\text{mid}}\rceil +\frac{d_{n-1}}{\text{mid}}$. Return $\mathbf{T}\le \text{hour}$.
Koko Eating Bananas (piles, $H$)	Find $\min (k)$ such that $\text{hours\_spent}\le H$	Calculate $T=\sum \lceil \frac{p_i}{\text{mid}}\rceil$. Return $\mathbf{T}\le \mathbf{H}$.
Minimum Time for Trips (time, totalTrips)	Find $\min (\text{time})$ such that $\text{trips\_made}\ge \text{totalTrips}$	Calculate $N=\sum \lfloor \frac{\text{mid}}{t_i}\rfloor$. Return $\mathbf{N}\ge \text{totalTrips}$.

🧩 Snippet B: The Search Bounds (left and right)

Problem	left (Minimum Possible Answer)	right (Maximum Possible Answer)
Minimum Speed to Arrive	$1$	$10^7$ (From problem constraint)
Koko Eating Bananas	$1$	$\max (\text{piles})$ (The fastest speed needed)
Minimum Time for Trips	$1$	$\min (\text{time})\times \text{totalTrips}$ (A safe upper bound)