Binary Search Patterns: 3 Templates and Bisect-on-Answer

def search(nums: list[int], target: int) -> int:
    """
    Template 1: find exact target in sorted array.
    Loop invariant: target is in nums[left..right] if it exists.
    Terminates when left > right (target not found).
    Time: O(log n), Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2  # avoids overflow in Java/C++
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # target not found

def find_first_true(nums: list[int], predicate) -> int:
    """
    Template 2: find leftmost index where predicate(nums[i]) is True.
    Assumes predicate is False for a prefix, True for a suffix (monotonic).

    Loop invariant:
      - predicate is False for everything BEFORE left
      - predicate is True for everything FROM right onward (once set)
    After loop: left == right == answer.

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

    while left < right:
        mid = left + (right - left) // 2
        if predicate(nums[mid]):
            right = mid      # mid might be the answer; don't skip it
        else:
            left = mid + 1   # mid is False, safe to skip

    # Post-loop: left == right. Check if predicate holds (it might not if
    # no element satisfies the predicate).
    return left if predicate(nums[left]) else -1

# Example: find leftmost position to insert target (bisect_left equivalent)
def bisect_left(nums: list[int], target: int) -> int:
    left, right = 0, len(nums)  # right = len(nums) allows insert-at-end
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            right = mid
        else:
            left = mid + 1
    return left

def ship_within_days(weights: list[int], days: int) -> int:
    """
    LC 1011 — minimum ship capacity to deliver all packages in <= days days.

    Key insight: binary search on CAPACITY, not on the array.
    - If capacity C works (can ship all in <= days), C+1 also works.
    - Predicate: can_ship(C) = True iff we can partition weights into
      at most 'days' groups each summing <= C.

    Search space: [max(weights), sum(weights)]
      - Lower bound: must carry heaviest single package
      - Upper bound: carry everything in one day

    Time: O(n * log(sum(weights))), Space: O(1)
    """
    def can_ship(capacity: int) -> bool:
        days_needed, current_load = 1, 0
        for w in weights:
            if current_load + w > capacity:
                days_needed += 1
                current_load = 0
            current_load += w
        return days_needed <= days

    left, right = max(weights), sum(weights)
    while left < right:
        mid = left + (right - left) // 2
        if can_ship(mid):
            right = mid      # mid works, try smaller
        else:
            left = mid + 1   # mid too small
    return left

def search_rotated(nums: list[int], target: int) -> int:
    """
    LC 33 — search in rotated sorted array. No duplicates.

    Key insight: split at mid → one half is ALWAYS sorted.
    Determine which half is sorted, check if target is in that half,
    then binary search the appropriate half.

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

    while left <= right:  # Template 1: exact target
        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  # target in sorted left half
            else:
                left = mid + 1   # target in right half
        else:
            # Right half [mid..right] is sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1   # target in sorted right half
            else:
                right = mid - 1  # target in left half

    return -1

def search_range(nums: list[int], target: int) -> list[int]:
    """
    LC 34 — find first and last position of target in sorted array.
    Two separate binary searches: leftmost and rightmost occurrence.
    Time: O(log n), Space: O(1)
    """
    def find_leftmost(target: int) -> int:
        left, right = 0, len(nums) - 1
        result = -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                result = mid   # record and keep searching left
                right = mid - 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return result

    def find_rightmost(target: int) -> int:
        left, right = 0, len(nums) - 1
        result = -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                result = mid   # record and keep searching right
                left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return result

    return [find_leftmost(target), find_rightmost(target)]

def find_peak_element(nums: list[int]) -> int:
    """
    LC 162 — find peak element (greater than both neighbors).
    Array edges are treated as -infinity.
    May return ANY peak if multiple exist.

    Key: binary search on UNSORTED array using a directional decision.
    If nums[mid] < nums[mid+1]: peak is to the RIGHT (move left up)
    If nums[mid] > nums[mid+1]: peak is at mid or to the LEFT (move right down)

    Loop invariant: a peak always exists in [left, right].
    Time: O(log n), Space: O(1)
    """
    left, right = 0, len(nums) - 1

    while left < right:  # Template 2
        mid = left + (right - left) // 2
        # mid < right is guaranteed, so mid+1 is always valid
        if nums[mid] < nums[mid + 1]:
            left = mid + 1   # peak is to the right
        else:
            right = mid      # nums[mid] >= nums[mid+1]: peak at mid or left

    return left  # left == right == peak index

def find_median_sorted_arrays(nums1: list[int], nums2: list[int]) -> float:
    """
    LC 4 — median of two sorted arrays in O(log(min(m,n))).

    Binary search on partition index of the SMALLER array.
    Valid partition: max(left_A, left_B) <= min(right_A, right_B)

    Time: O(log(min(m,n))), Space: O(1)
    """
    # Ensure nums1 is the smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    half_len = (m + n + 1) // 2  # left half size

    left, right = 0, m
    while left <= right:
        i = left + (right - left) // 2   # partition index in nums1
        j = half_len - i                  # partition index in nums2

        # Edge: use -inf / +inf for boundaries
        left_a  = nums1[i - 1] if i > 0 else float('-inf')
        right_a = nums1[i]     if i < m else float('inf')
        left_b  = nums2[j - 1] if j > 0 else float('-inf')
        right_b = nums2[j]     if j < n else float('inf')

        if left_a <= right_b and left_b <= right_a:
            # Valid partition found
            left_max = max(left_a, left_b)
            if (m + n) % 2 == 1:
                return float(left_max)
            right_min = min(right_a, right_b)
            return (left_max + right_min) / 2.0
        elif left_a > right_b:
            right = i - 1  # i too large, move left
        else:
            left = i + 1   # i too small, move right

    raise ValueError("Input arrays are not sorted")