Binary Search Pattern¶

def binary_search(arr: list[int], target: int) -> int:
    """
    Find index of target in sorted arr, or -1 if absent.
    Time: O(log n), Space: O(1)
    """
    left, right = 0, len(arr) - 1  # inclusive bounds

    while left <= right:           # <= because both bounds are valid candidates
        mid = left + (right - left) // 2  # avoids overflow, same as (l+r)//2 in Python
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1          # target is to the right, exclude mid
        else:
            right = mid - 1         # target is to the left, exclude mid

    return -1  # not found

def binary_search_on_answer(lo: int, hi: int, feasible) -> int:
    """
    Find the smallest value in [lo, hi] for which feasible(value) is True,
    given feasible() is monotonic: False False False ... True True True.
    Time: O(log(hi - lo)) * cost of feasible()
    """
    while lo < hi:                  # < because we converge to a single point
        mid = lo + (hi - lo) // 2
        if feasible(mid):
            hi = mid                 # mid works; try to find something smaller (or equal)
        else:
            lo = mid + 1              # mid doesn't work; answer must be larger

    return lo  # lo == hi, the boundary

def search_rotated(nums: list[int], target: int) -> int:
    """
    Array was sorted, then rotated at an unknown pivot, e.g. [4,5,6,7,0,1,2].
    Insight: at any mid, AT LEAST ONE half is still normally sorted.
    Determine which half is sorted, then check if target lies in that
    sorted half's range to decide which side to search.
    Time: O(log n), Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:  # left half [left..mid] is sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:                         # right half [mid..right] is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

import math

def min_eating_speed(piles: list[int], h: int) -> int:
    """
    Koko eats at speed k bananas/hour; find minimum k so she finishes
    all piles within h hours.
    Predicate: feasible(k) = "can Koko finish within h hours at speed k?"
    This is monotonic: if speed k works, any speed > k also works.
    Search space: k in [1, max(piles)].
    Time: O(n log(max(piles))), Space: O(1)
    """
    def hours_needed(k: int) -> int:
        return sum(math.ceil(pile / k) for pile in piles)

    lo, hi = 1, max(piles)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if hours_needed(mid) <= h:
            hi = mid          # mid works; try smaller speed
        else:
            lo = mid + 1       # mid too slow; need faster speed

    return lo

def ship_within_days(weights: list[int], days: int) -> int:
    """
    Find minimum ship capacity so all packages ship (in original order,
    without splitting) within `days` days.
    Predicate: feasible(capacity) = "can we ship within `days` days?"
    Search space: [max(weights), sum(weights)] — capacity can't be less
    than the heaviest single package, and never needs to exceed the total.
    Time: O(n log(sum(weights))), Space: O(1)
    """
    def days_needed(capacity: int) -> int:
        days_used, current_load = 1, 0
        for w in weights:
            if current_load + w > capacity:
                days_used += 1
                current_load = 0
            current_load += w
        return days_used

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if days_needed(mid) <= days:
            hi = mid
        else:
            lo = mid + 1

    return lo

# Always check:
# 1. Empty array (len == 0) -> return -1 / not found immediately
# 2. Single element array
# 3. Target smaller than all elements / larger than all elements
# 4. Duplicate elements (which occurrence should you return?)
# 5. For "on the answer": verify lo/hi bounds are both achievable
#    (e.g. hi must itself satisfy feasible(hi), or the loop can't converge)

def robust_binary_search(arr, target):
    if not arr:
        return -1
    # ... rest of solution