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.

---

Pattern 4 — Rotated Sorted Array

Array was sorted then rotated at unknown pivot. Determine which half is sorted, then decide where target lives.

# LC 33 — Search in Rotated Sorted Array
def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1   # target in sorted left half
            else:
                left = mid + 1    # target in right half
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1    # target in sorted right half
            else:
                right = mid - 1   # target in left half
    return -1

Key insight: One half is always sorted. Check which — then determine if target falls in that sorted range. If yes, search there; if not, search the other half.

---

Pattern 5 — Peak Element / Find Minimum in Rotated

# LC 153 — Find Minimum in Rotated Sorted Array
def findMin(nums):
    left, right = 0, len(nums) - 1
    while left < right:            # NOT <=
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1         # min is in right half
        else:
            right = mid            # mid might BE the min — don't exclude it
    return nums[left]

Key insight: Compare mid to right (not left). If nums[mid] > nums[right], the rotation happened in the right half so min is there. Otherwise min is in left half (mid could be it, so right = mid not mid - 1).

---

Python bisect Module

import bisect

# bisect_left: index of first element >= target
# bisect_right: index of first element > target
arr = [1, 3, 3, 5, 7]
bisect.bisect_left(arr, 3)   # 1  (first 3)
bisect.bisect_right(arr, 3)  # 3  (after last 3)

# Insert into sorted position
bisect.insort(arr, 4)        # arr = [1, 3, 3, 4, 5, 7]

Use bisect_left when you want leftmost position (first occurrence, lower_bound). Use bisect_right when you want rightmost position (after last occurrence, upper_bound).

---

Interview Opener

"I'll binary search the answer space — define lo/hi as the range of possible answers, define a feasibility check, and shrink the range each iteration to O(log N)."

---

Senior Tricks

• mid = left + (right - left) // 2 — never (left + right) // 2 (overflow risk in other langs)
• while left < right vs left <= right: Use <= when you return inside the loop on ==. Use < when you narrow without a direct return (find min/max position).
• right = mid vs right = mid - 1: Use mid when mid itself could be the answer (don't exclude it). Use mid - 1 when mid is confirmed NOT the answer.

---

Problems