Binary Search Patterns: Complete Reference¶

def binary_search_first_true(left: int, right: int, predicate) -> int:
    """
    Find the first position where predicate(x) is True.

    This is the canonical binary search template. All other variations
    are specializations of this pattern with specific predicates.

    Requirements:
    - predicate(x) must be monotonic: once True, stays True
    - Search space [left, right] where answer exists or returns right+1

    Invariant:
    - At all times, if answer exists, it's in [left, right]
    - predicate(left - 1) is False (or left is minimum)
    - predicate(right + 1) is True (or right is maximum)

    Algorithm:
    1. Compute mid = left + (right - left) // 2 (overflow-safe)
    2. If predicate(mid) is True, answer could be mid or earlier
       → search left half: right = mid
    3. If predicate(mid) is False, answer must be after mid
       → search right half: left = mid + 1
    4. Terminate when left == right (single candidate remaining)

    Time Complexity: O(log n) iterations × O(predicate)
    Space Complexity: O(1)

    Args:
        left: Lower bound of search space (inclusive)
        right: Upper bound of search space (inclusive)
        predicate: Monotonic function returning bool

    Returns:
        First index where predicate is True, or right + 1 if never True
    """
    # Search space: [left, right]
    while left < right:
        # Overflow-safe midpoint calculation
        mid = left + (right - left) // 2

        if predicate(mid):
            # predicate(mid) is True
            # Answer could be mid or something earlier
            # Maintain invariant: answer is in [left, mid]
            right = mid
        else:
            # predicate(mid) is False
            # Answer must be strictly after mid
            # Maintain invariant: answer is in [mid + 1, right]
            left = mid + 1

    # left == right: only one candidate remains
    # This is the first position where predicate might be True
    return left

def binary_search_exact(arr: list[int], target: int) -> int:
    """
    Find index of target in sorted array, or -1 if not found.

    This is a specialization of predicate boundary search where:
    - Predicate: arr[mid] >= target
    - After finding boundary, verify arr[boundary] == target

    Time Complexity: O(log n)
    Space Complexity: O(1)

    Args:
        arr: Sorted array (ascending)
        target: Value to find

    Returns:
        Index of target, or -1 if not found
    """
    if not arr:
        return -1

    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid  # Found exact match
        elif arr[mid] < target:
            left = mid + 1  # Target is in right half
        else:
            right = mid - 1  # Target is in left half

    return -1  # Not found

def lower_bound(arr: list[int], target: int) -> int:
    """
    Find the first index where arr[i] >= target.

    This is the standard library equivalent of C++ std::lower_bound.
    If target is not found, returns the insertion point.

    Predicate: arr[mid] >= target

    Properties:
    - All elements before result are < target
    - All elements from result onwards are >= target
    - Result can be len(arr) if all elements < target

    Time Complexity: O(log n)
    Space Complexity: O(1)

    Args:
        arr: Sorted array (ascending)
        target: Value to search for

    Returns:
        First index i where arr[i] >= target, or len(arr) if none
    """
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] >= target:
            # arr[mid] is a candidate (it's >= target)
            # But there might be an earlier one
            right = mid
        else:
            # arr[mid] < target, so answer must be after mid
            left = mid + 1

    return left

def upper_bound(arr: list[int], target: int) -> int:
    """
    Find the first index where arr[i] > target.

    This is the standard library equivalent of C++ std::upper_bound.

    Predicate: arr[mid] > target

    Properties:
    - All elements before result are <= target
    - All elements from result onwards are > target
    - Result can be len(arr) if all elements <= target

    Use with lower_bound to find range of target:
    - First occurrence: lower_bound(arr, target)
    - Last occurrence: upper_bound(arr, target) - 1
    - Count of target: upper_bound - lower_bound

    Time Complexity: O(log n)
    Space Complexity: O(1)

    Args:
        arr: Sorted array (ascending)
        target: Value to search for

    Returns:
        First index i where arr[i] > target, or len(arr) if none
    """
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] > target:
            # arr[mid] is a candidate (it's > target)
            right = mid
        else:
            # arr[mid] <= target, so answer must be after mid
            left = mid + 1

    return left

def search_range(nums: list[int], target: int) -> list[int]:
    """
    Find the starting and ending position of target in sorted array.

    Algorithm:
    1. Use lower_bound to find first occurrence
    2. Use upper_bound to find position after last occurrence
    3. Verify target actually exists

    Time Complexity: O(log n)
    Space Complexity: O(1)

    Args:
        nums: Sorted array (ascending)
        target: Value to find range for

    Returns:
        [first, last] indices, or [-1, -1] if not found
    """
    if not nums:
        return [-1, -1]

    # Find first position where nums[i] >= target
    first = lower_bound(nums, target)

    # Check if target exists
    if first == len(nums) or nums[first] != target:
        return [-1, -1]

    # Find first position where nums[i] > target
    # Last occurrence is one position before
    last = upper_bound(nums, target) - 1

    return [first, last]

def search_insert(nums: list[int], target: int) -> int:
    """
    Find index where target is or would be inserted.

    This is exactly lower_bound: first position where nums[i] >= target.

    Time Complexity: O(log n)
    Space Complexity: O(1)

    Args:
        nums: Sorted array of distinct integers
        target: Value to find or insert

    Returns:
        Index of target or insertion position
    """
    return lower_bound(nums, target)

def search_rotated(nums: list[int], target: int) -> int:
    """
    Search for target in rotated sorted array (no duplicates).

    Algorithm:
    1. Find mid
    2. Determine which half is sorted (compare arr[left] with arr[mid])
    3. Check if target is in the sorted half
    4. Narrow search to the appropriate half

    Key Insight:
    - If left half is sorted AND target is in [arr[left], arr[mid]): go left
    - If left half is sorted AND target is NOT in range: go right
    - If right half is sorted AND target is in (arr[mid], arr[right]]: go right
    - If right half is sorted AND target is NOT in range: go left

    Invariant:
    - If target exists, it's in [left, right]

    Why this doesn't skip the answer:
    - We only eliminate a half when we're CERTAIN target isn't there
    - The sorted half gives us exact boundaries to check

    Time Complexity: O(log n)
    Space Complexity: O(1)

    Args:
        nums: Rotated sorted array (distinct elements)
        target: Value to find

    Returns:
        Index of target, or -1 if not found
    """
    if not nums:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # Determine which half is sorted
        if nums[left] <= nums[mid]:
            # Left half [left, mid] is sorted
            if nums[left] <= target < nums[mid]:
                # Target is in the sorted left half
                right = mid - 1
            else:
                # Target is in the right half
                left = mid + 1
        else:
            # Right half [mid, right] is sorted
            if nums[mid] < target <= nums[right]:
                # Target is in the sorted right half
                left = mid + 1
            else:
                # Target is in the left half
                right = mid - 1

    return -1

def search_rotated_with_duplicates(nums: list[int], target: int) -> bool:
    """
    Search for target in rotated sorted array (may have duplicates).

    Key Challenge:
    When nums[left] == nums[mid] == nums[right], we cannot determine
    which half is sorted. In this case, we must shrink linearly.

    Example: [1, 0, 1, 1, 1] with target = 0
    - left=0, right=4, mid=2
    - nums[0]=1, nums[2]=1, nums[4]=1
    - Cannot tell if [1,0,1] or [1,1,1] is sorted

    Solution: When this ambiguity occurs, shrink search space by 1.

    Worst Case: O(n) when all elements are equal except one
    Average Case: O(log n) when duplicates are sparse

    Time Complexity: O(n) worst case, O(log n) average
    Space Complexity: O(1)

    Args:
        nums: Rotated sorted array (may have duplicates)
        target: Value to find

    Returns:
        True if target exists, False otherwise
    """
    if not nums:
        return False

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return True

        # Handle ambiguous case: can't determine sorted half
        if nums[left] == nums[mid] == nums[right]:
            left += 1
            right -= 1
        elif nums[left] <= nums[mid]:
            # Left half is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # Right half is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return False

def search_rotated_two_phase(nums: list[int], target: int) -> int:
    """
    Two-phase approach: find pivot, then search in appropriate half.

    Phase 1: Find the pivot (minimum element)
    Phase 2: Binary search in the correct half

    Time Complexity: O(log n)
    Space Complexity: O(1)
    """
    if not nums:
        return -1

    n = len(nums)

    # Phase 1: Find pivot (index of minimum element)
    left, right = 0, n - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    pivot = left

    # Phase 2: Determine which half to search
    left, right = 0, n - 1
    if target >= nums[pivot] and target <= nums[n - 1]:
        left = pivot
    else:
        right = pivot - 1

    # Phase 3: Standard binary search
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

def binary_search_on_answer(lo: int, hi: int, is_feasible) -> int:
    """
    Find the minimum value in [lo, hi] where is_feasible(x) is True.

    Requirements:
    - is_feasible is monotonic: if is_feasible(x), then is_feasible(x+1)
    - At least one value in [lo, hi] must be feasible

    This is exactly predicate boundary search over the answer space.

    Time Complexity: O(log(hi - lo) × feasibility_check)
    Space Complexity: O(1)

    Args:
        lo: Minimum possible answer (inclusive)
        hi: Maximum possible answer (inclusive)
        is_feasible: Function returning True if answer x is feasible

    Returns:
        Minimum feasible answer
    """
    while lo < hi:
        mid = lo + (hi - lo) // 2

        if is_feasible(mid):
            # mid works, but maybe something smaller also works
            hi = mid
        else:
            # mid doesn't work, need larger value
            lo = mid + 1

    return lo

def min_eating_speed(piles: list[int], h: int) -> int:
    """
    Find minimum eating speed k to finish all bananas within h hours.

    Problem:
    - Each hour, Koko eats k bananas from one pile
    - If pile has less than k, she eats the whole pile and waits
    - Find minimum k such that total hours <= h

    Insight:
    - Answer space: [1, max(piles)]
    - If k=1 works, any larger k also works (monotonic)
    - Feasibility check: sum(ceil(pile/k) for pile in piles) <= h

    Predicate: can_finish(k) = total_hours(k) <= h

    Time Complexity: O(n × log(max(piles)))
    Space Complexity: O(1)

    Args:
        piles: Array of banana pile sizes
        h: Available hours

    Returns:
        Minimum eating speed
    """
    def hours_needed(speed: int) -> int:
        """Calculate total hours needed at given speed."""
        total = 0
        for pile in piles:
            # Ceiling division: (pile + speed - 1) // speed
            total += (pile + speed - 1) // speed
        return total

    def can_finish(speed: int) -> bool:
        """Check if Koko can finish within h hours at this speed."""
        return hours_needed(speed) <= h

    # Answer space: [1, max(piles)]
    # At speed = max(piles), each pile takes 1 hour
    lo, hi = 1, max(piles)

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if can_finish(mid):
            # This speed works, try to find a smaller one
            hi = mid
        else:
            # Too slow, need faster eating
            lo = mid + 1

    return lo

def ship_within_days(weights: list[int], days: int) -> int:
    """
    Find minimum ship capacity to ship all packages within given days.

    Problem:
    - Packages must be shipped in order (no reordering)
    - Each day, ship consecutive packages up to capacity
    - Find minimum capacity to finish in exactly `days` days

    Insight:
    - Minimum capacity = max(weights) (must fit largest package)
    - Maximum capacity = sum(weights) (ship everything in one day)
    - If capacity C works, C+1 also works (monotonic)

    Feasibility Check:
    - Greedily fill each day up to capacity
    - Count days needed
    - Return days_needed <= days

    Time Complexity: O(n × log(sum(weights)))
    Space Complexity: O(1)

    Args:
        weights: Array of package weights (in order)
        days: Number of days to ship all packages

    Returns:
        Minimum ship capacity
    """
    def days_needed(capacity: int) -> int:
        """Calculate days needed to ship all packages at given capacity."""
        day_count = 1
        current_load = 0

        for weight in weights:
            if current_load + weight > capacity:
                # Start a new day
                day_count += 1
                current_load = weight
            else:
                current_load += weight

        return day_count

    def can_ship(capacity: int) -> bool:
        """Check if all packages can be shipped within `days` days."""
        return days_needed(capacity) <= days

    # Answer space: [max(weights), sum(weights)]
    lo = max(weights)  # Must fit largest package
    hi = sum(weights)  # Can ship everything in one day

    while lo < hi:
        mid = lo + (hi - lo) // 2

        if can_ship(mid):
            # This capacity works, try smaller
            hi = mid
        else:
            # Need more capacity
            lo = mid + 1

    return lo

def find_peak_element(nums: list[int]) -> int:
    """
    Find a peak element and return its index.

    A peak element is strictly greater than its neighbors.
    The array may contain multiple peaks; return any one.

    Boundary conditions:
    - nums[-1] = nums[n] = -infinity (conceptually)
    - So nums[0] is a peak if nums[0] > nums[1]
    - And nums[n-1] is a peak if nums[n-1] > nums[n-2]

    Algorithm:
    - If nums[mid] < nums[mid + 1]: ascending slope, peak is on the right
    - If nums[mid] > nums[mid + 1]: descending slope, mid could be peak
    - Continue until single element remains

    Why we never skip a peak:
    - When we go right (ascending), we follow towards a peak
    - When we go left (descending), mid might be the peak, so we keep it

    Invariant:
    - There's always at least one peak in [left, right]

    Time Complexity: O(log n)
    Space Complexity: O(1)

    Args:
        nums: Array where nums[i] != nums[i + 1] for all valid i

    Returns:
        Index of any peak element
    """
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < nums[mid + 1]:
            # Ascending slope: peak must be in [mid + 1, right]
            # We can exclude mid because mid + 1 is greater
            left = mid + 1
        else:
            # Descending slope: peak is in [left, mid]
            # mid could be the peak, so include it
            right = mid

    # left == right: only one candidate, must be a peak
    return left

def peak_index_in_mountain_array(arr: list[int]) -> int:
    """
    Find the peak index in a mountain array.

    Mountain array: arr[0] < arr[1] < ... < arr[peak] > ... > arr[n-1]
    Guaranteed to have exactly one peak.

    Same logic as find_peak_element.

    Time Complexity: O(log n)
    Space Complexity: O(1)
    """
    left, right = 0, len(arr) - 1

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] < arr[mid + 1]:
            left = mid + 1
        else:
            right = mid

    return left

# Left-biased (rounds down) - Standard
mid = left + (right - left) // 2

# Right-biased (rounds up)
mid = left + (right - left + 1) // 2

def first_true(lo, hi, predicate):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if predicate(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def lower_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] >= target:
            hi = mid
        else:
            lo = mid + 1
    return lo

def upper_bound(arr, target):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] > target:
            hi = mid
        else:
            lo = mid + 1
    return lo

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:  # Left sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:  # Right sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

def min_feasible(lo, hi, is_feasible):
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

def find_peak(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] < nums[mid + 1]:
            lo = mid + 1
        else:
            hi = mid
    return lo

# Invariant: answer is in [left, right] (inclusive both ends)
left, right = 0, len(arr) - 1
while left <= right:
    mid = (left + right) // 2
    if condition(mid):
        right = mid - 1  # Exclude mid, search [left, mid-1]
    else:
        left = mid + 1   # Exclude mid, search [mid+1, right]
# Loop ends when left > right (empty interval)

# Invariant: answer is in [left, right) or [left, right]
left, right = 0, len(arr)  # Note: right = len(arr), not len(arr)-1
while left < right:
    mid = (left + right) // 2
    if condition(mid):
        right = mid        # Keep mid in range, search [left, mid]
    else:
        left = mid + 1     # Exclude mid, search [mid+1, right]
# Loop ends when left == right (single candidate)

# Find FIRST occurrence of target
while left < right:
    mid = (left + right) // 2
    if arr[mid] >= target:  # Include mid in left part
        right = mid
    else:
        left = mid + 1

# Find LAST occurrence of target
while left < right:
    mid = (left + right + 1) // 2  # Bias right to avoid infinite loop
    if arr[mid] <= target:  # Include mid in right part
        left = mid
    else:
        right = mid - 1

def exists(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return True  # or return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False  # or return -1

def find_minimum(low, high, feasible):
    while low < high:
        mid = (low + high) // 2
        if feasible(mid):
            high = mid      # mid works, try smaller
        else:
            low = mid + 1   # mid doesn't work, need larger
    return low

# Find first speed where Koko can finish
# Predicate: can_finish(speed) returns True/False
# [F, F, F, T, T, T, T] → find first T
def first_true(lo, hi, predicate):
    while lo < hi:
        mid = (lo + hi) // 2
        if predicate(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

# Find maximum pages per day such that reading finishes
# [T, T, T, T, F, F, F] → find last T
def last_true(lo, hi, predicate):
    while lo < hi:
        mid = (lo + hi + 1) // 2  # Bias right
        if predicate(mid):
            lo = mid
        else:
            hi = mid - 1
    return lo

left, right = 0, len(arr) - 1  # or len(arr) for half-open

# Bounds come from problem constraints, NOT array length
left = min_possible_answer
right = max_possible_answer

# 875. Koko Eating Bananas
# Speed must be at least 1 (can't eat 0 bananas/hour)
# Speed at most max(piles) (can finish largest pile in 1 hour)
left, right = 1, max(piles)

# 1011. Capacity to Ship Packages
# Capacity must hold heaviest package
# Capacity at most total weight (ship everything in 1 day)
left, right = max(weights), sum(weights)

# 410. Split Array Largest Sum
# Min sum is largest element (one per subarray)
# Max sum is total (everything in one subarray)
left, right = max(nums), sum(nums)

while left < right:
    mid = (left + right) // 2
    if predicate(mid):  # mid is True
        right = mid     # Answer could be mid or before, keep mid
    else:               # mid is False
        left = mid + 1  # Answer must be after mid, exclude mid

while left < right:
    mid = (left + right + 1) // 2  # Bias right
    if predicate(mid):  # mid is True
        left = mid      # Answer could be mid or after, keep mid
    else:               # mid is False
        right = mid - 1 # Answer must be before mid, exclude mid

def solve(nums, constraint):
    left, right = min_answer, max_answer

    def is_feasible(candidate):
        """Greedy check: can we achieve this candidate value?"""
        # Use greedy algorithm to verify feasibility
        return greedy_check(nums, candidate, constraint)

    while left < right:
        mid = (left + right) // 2
        if is_feasible(mid):
            right = mid      # or left = mid for maximize
        else:
            left = mid + 1   # or right = mid - 1 for maximize
    return left

def minEatingSpeed(piles, h):
    left, right = 1, max(piles)

    def can_finish(speed):
        # Greedy: eat each pile, count hours
        hours = sum((pile + speed - 1) // speed for pile in piles)
        return hours <= h

    while left < right:
        mid = (left + right) // 2
        if can_finish(mid):
            right = mid
        else:
            left = mid + 1
    return left

def shipWithinDays(weights, days):
    left, right = max(weights), sum(weights)

    def can_ship(capacity):
        # Greedy: load packages until capacity, count days
        day_count, current_load = 1, 0
        for w in weights:
            if current_load + w > capacity:
                day_count += 1
                current_load = 0
            current_load += w
        return day_count <= days

    while left < right:
        mid = (left + right) // 2
        if can_ship(mid):
            right = mid
        else:
            left = mid + 1
    return left

def splitArray(nums, k):
    left, right = max(nums), sum(nums)

    def can_split(max_sum):
        # Greedy: start new subarray when sum exceeds max_sum
        splits, current_sum = 1, 0
        for num in nums:
            if current_sum + num > max_sum:
                splits += 1
                current_sum = 0
            current_sum += num
        return splits <= k

    while left < right:
        mid = (left + right) // 2
        if can_split(mid):
            right = mid
        else:
            left = mid + 1
    return left

def is_feasible(limit):
    count = 1  # Start with 1 group/day/split
    current = 0

    for item in items:
        if current + item > limit:
            count += 1       # Start new group
            current = 0
        current += item

    return count <= allowed_groups

# Can't ship a package heavier than capacity
left = max(weights)

# Can't eat a pile bigger than speed × 1 hour
left = 1  # (or could be max(piles) if must finish each pile in 1 hour)

# Ship everything in 1 day
right = sum(weights)

# Finish largest pile in 1 hour
right = max(piles)

# If doing left = mid, use ceiling division
mid = (left + right + 1) // 2

# Verify both branches move boundaries
if condition:
    right = mid      # or right = mid - 1
else:
    left = mid + 1   # Must have + 1

# Check initial bounds include answer
assert left <= answer <= right

# Check predicate has transition
assert not predicate(left) and predicate(right)  # for first_true

# first_true: floor division, move right
mid = (left + right) // 2
right = mid

# last_true: ceiling division, move left
mid = (left + right + 1) // 2
left = mid

# Verify predicate is monotonic
# All False before all True (or vice versa)
[F, F, F, T, T, T]  # OK
[F, T, F, T, F, T]  # NOT OK - can't use binary search

# First occurrence: include mid in right part when equal
if arr[mid] >= target:
    right = mid

# Last occurrence: include mid in left part when equal
if arr[mid] <= target:
    left = mid