6. Binary Search

Key Insight

Binary search isn't just for sorted arrays — it's applicable any time the search space is monotonic (satisfies a predicate that flips from False to True or True to False exactly once). Always define the predicate f(mid) clearly before coding.

Complexity: $O(\log n)$ time, $O(1)$ space

---

6.1 Classic Templates

import bisect

# --- Standard binary search (find target or -1) ---
def binary_search(arr: list[int], target: int) -> int:
    l, r = 0, len(arr) - 1
    while l <= r:
        mid = l + (r - l) // 2  # avoids overflow (good habit)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1

# --- Find leftmost position where arr[i] >= target ---
def lower_bound(arr: list[int], target: int) -> int:
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] < target:
            l = mid + 1
        else:
            r = mid
    return l  # index of first element >= target

# --- Find leftmost position where arr[i] > target ---
def upper_bound(arr: list[int], target: int) -> int:
    l, r = 0, len(arr)
    while l < r:
        mid = (l + r) // 2
        if arr[mid] <= target:
            l = mid + 1
        else:
            r = mid
    return l  # index of first element > target

# Python's bisect module (preferred in CP)
# bisect.bisect_left(a, x)  ≡ lower_bound — leftmost index to insert x keeping sorted order
# bisect.bisect_right(a, x) ≡ upper_bound — rightmost index to insert x
# bisect.insort_left(a, x)  — insert x maintaining sorted order O(n) due to shift
pos = bisect.bisect_left([1,3,3,5,7], 3)   # 1 (first 3)
pos = bisect.bisect_right([1,3,3,5,7], 3)  # 3 (after last 3)

---

6.2 Binary Search on Answer

Insight: "Find minimum X such that condition holds" → binary search on X, validate with a checker function.

# --- Minimum capacity to ship packages in D days ---
def ship_within_days(weights: list[int], days: int) -> int:
    def can_ship(capacity: int) -> bool:
        ships, load = 1, 0
        for w in weights:
            if load + w > capacity:
                ships += 1; load = 0
            load += w
        return ships <= days

    l, r = max(weights), sum(weights)
    while l < r:
        mid = (l + r) // 2
        if can_ship(mid):
            r = mid
        else:
            l = mid + 1
    return l

# --- Koko eating bananas (minimum speed) ---
import math
def min_eating_speed(piles: list[int], h: int) -> int:
    def hours_needed(speed: int) -> int:
        return sum(math.ceil(p / speed) for p in piles)

    l, r = 1, max(piles)
    while l < r:
        mid = (l + r) // 2
        if hours_needed(mid) <= h:
            r = mid
        else:
            l = mid + 1
    return l

# --- Median of two sorted arrays --- O(log(min(m,n)))
def find_median_sorted(A: list[int], B: list[int]) -> float:
    if len(A) > len(B):
        A, B = B, A
    m, n = len(A), len(B)
    half = (m + n) // 2
    l, r = 0, m
    while l <= r:
        i = (l + r) // 2
        j = half - i
        A_left  = A[i-1] if i > 0 else float("-inf")
        A_right = A[i]   if i < m else float("inf")
        B_left  = B[j-1] if j > 0 else float("-inf")
        B_right = B[j]   if j < n else float("inf")
        if A_left <= B_right and B_left <= A_right:
            if (m + n) % 2:
                return float(min(A_right, B_right))
            return (max(A_left, B_left) + min(A_right, B_right)) / 2
        elif A_left > B_right:
            r = i - 1
        else:
            l = i + 1

---

6.3 Binary Search on Rotated / Non-Standard Arrays

# --- Search in rotated sorted array ---
def search_rotated(nums: list[int], target: int) -> int:
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid
        if nums[l] <= nums[mid]:          # left half sorted
            if nums[l] <= target < nums[mid]:
                r = mid - 1
            else:
                l = mid + 1
        else:                              # right half sorted
            if nums[mid] < target <= nums[r]:
                l = mid + 1
            else:
                r = mid - 1
    return -1

---

6.4 Key CP Patterns

Template	When
l <= r, return on match	Exact value search
l < r, converge to single point	Lower/upper bound, minimise/maximise
Binary search on answer	"Minimum/maximum X such that..."
Rotated array	Both halves check sorted side

---