Transition Point Recipe Overview and Analysis

The transition point recipe is a universal pattern that works for all binary search problems. Understanding this recipe eliminates confusion about which template to use.

The Core Pattern

Binary search finds a transition point where a property changes from False to True (or vice versa).

[False, False, False, True, True, True]
                    ↑
            Transition Point

The Three Templates

Template 1: Classic Binary Search

Use when: Finding exact value or simple condition.

def binary_search_template_1(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Key points:

• Loop while left <= right
• Can return mid immediately when found
• After loop, left > right (no elements left)

Template 2: Find Boundary (Left-most/Right-most)

Use when: Finding first/last occurrence, insertion point, or boundaries.

def binary_search_template_2(nums, target):
    """Find leftmost (smallest) index where condition is true"""
    left, right = 0, len(nums)

    while left < right:
        mid = left + (right - left) // 2

        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid

    # left is the leftmost position where nums[left] >= target
    return left

Key points:

• Loop while left < right (not <=)
• Never return mid in loop
• right = mid (not mid - 1)
• After loop, left == right

Template 3: Find with Neighbors

Use when: Need to check mid's neighbors.

def binary_search_template_3(nums, target):
    """Need to check mid-1 and mid+1"""
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left + 1 < right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid
        else:
            right = mid

    # Check remaining elements
    if nums[left] == target:
        return left
    if nums[right] == target:
        return right

    return -1

Key points:

• Loop while left + 1 < right (leaves 2 elements)
• left = mid and right = mid (not +/- 1)
• Check both left and right after loop

Choosing the Right Template

Need to return immediately when found?
├─ Yes → Template 1
│
└─ No → Finding boundary/insertion point?
   ├─ Yes → Template 2
   │
   └─ No → Need to check neighbors?
      └─ Yes → Template 3

Transition Point Analysis

The key insight: Every binary search problem is about finding a transition point.

• Template 1: Transition from "not found" to "found"
• Template 2: Transition from "condition false" to "condition true"
• Template 3: Transition point requires neighbor context

Common Patterns

Pattern 1: Exact Match

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

Pattern 2: Find Leftmost

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

Pattern 3: Find Rightmost

while left < right:
    mid = left + (right - left) // 2
    if nums[mid] <= target:
        left = mid + 1
    else:
        right = mid
left -= 1  # Adjust to last occurrence

Key Takeaway

Master these three templates and you can solve any binary search problem. The transition point recipe helps you identify which template to use based on what you're searching for.