Binary Search

🧠 Spot It

Use Binary Search when:

1. Input is sorted (array, range, search space)
2. Problem asks for a specific value, or min/max that satisfies a condition
3. Brute force is O(N) or O(N²) — binary search brings it to O(log N)

Key insight: Binary search isn't just for sorted arrays — it's a search space reduction tool.

---

Pattern 1 — Classic Binary Search

Find a target in a sorted array.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # avoid overflow
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

---

Pattern 2 — Find Boundary (leftmost / rightmost)

Used when duplicates exist or you need first/last occurrence.

def find_left_boundary(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # keep searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

---

Pattern 3 — Binary Search on Answer (Search Space)

Problem gives a range of possible answers — binary search the answer space.

Template:

def binary_search_answer(lo, hi):
    result = -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if is_feasible(mid):   # define your condition
            result = mid
            hi = mid - 1       # or lo = mid + 1 depending on min/max
        else:
            lo = mid + 1
    return result

Classic example: Koko Eating Bananas — binary search on eating speed, check if feasible.

---

Senior Tricks

• mid = left + (right - left) // 2 — never (left + right) // 2 (overflow risk in other langs)
• Rotated sorted array — check which half is sorted, then decide which way to search
• bisect module in Python: bisect_left, bisect_right for production code

---

Problems

---

Notes

<!-- Add your own observations as you solve problems -->