Binary Search Off-by-One Errors: The Complete Fix for left, right, and mid

Off-by-one errors are the most common bugs in binary search implementations. A single character difference—mid vs mid + 1, or < vs <=—changes everything.

You understand binary search conceptually. But when you code it, you get wrong answers on edge cases, infinite loops, or array index out of bounds. The problem? Pointer update logic is subtle, and most tutorials don't explain the underlying principles.

This guide will teach you the three pointer update patterns, when to use each, how to match them with loop conditions, and a decision framework that works every time.

TL;DR

The three safe patterns:

Pattern 1: Classic (both pointers exclude mid)

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

Pattern 2: Lower bound (right keeps mid)

while left < right:
    mid = left + (right - left) // 2
    if arr[mid] < target:
        left = mid + 1  # Exclude mid
    else:
        right = mid  # Keep mid

Pattern 3: Upper bound (right keeps mid)

while left < right:
    mid = left + (right - left) // 2
    if arr[mid] <= target:
        left = mid + 1  # Exclude mid
    else:
        right = mid  # Keep mid

Rule: If either pointer is set to mid, use left < right. Otherwise use left <= right.

Why Off-by-One Errors Happen

The Root Cause

Binary search maintains a search space [left, right]. Each iteration:

1. Calculates mid
2. Decides which half contains the target
3. Updates left or right to exclude the wrong half

Off-by-one errors occur when:

• You exclude too much (miss the answer)
• You exclude too little (infinite loop)
• Loop condition doesn't match pointer updates

Example: The Classic Mistake

❌ Wrong:

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

What breaks:

Array: [1, 2, 3], target = 3

left=0, right=2, mid=1
  arr[1]=2 < 3 → left=2

left=2, right=2 → loop stops (left < right is false)
Never checked arr[2]=3!

The fix: Use left <= right when both pointers exclude mid.

The Three Pointer Update Patterns

Pattern 1: left = mid + 1, right = mid - 1

Use case: Classic binary search (find exact element)

Loop condition: while left <= right

Why it works:

• Both pointers exclude mid from next search
• When left > right, we've checked all elements
• Can use <= because pointers will cross

Complete template:

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

Trace example:

Array: [1, 3, 5, 7, 9], target = 7

left=0, right=4, mid=2
  arr[2]=5 < 7 → left=3

left=3, right=4, mid=3
  arr[3]=7 == 7 → return 3 ✓

Pattern 2: left = mid + 1, right = mid

Use case: Lower bound, upper bound, first occurrence

Loop condition: while left < right

Why it works:

• right = mid keeps mid as potential answer
• left = mid + 1 excludes mid when it's too small
• When left == right, that's the answer
• Must use < (not <=) to avoid infinite loop

Complete template (lower bound):

def lower_bound(arr, target):
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1  # Exclude mid and everything left
        else:
            right = mid  # Keep mid as potential answer
    
    return left  # left == right when loop ends

Why right = mid not mid - 1?

Because arr[mid] might be the first occurrence! We can't exclude it.

Trace example:

Array: [1, 2, 2, 2, 3], target = 2

left=0, right=5, mid=2
  arr[2]=2 >= 2 → right=2

left=0, right=2, mid=1
  arr[1]=2 >= 2 → right=1

left=0, right=1, mid=0
  arr[0]=1 < 2 → left=1

left=1, right=1 → stop
Return 1 (first occurrence) ✓

Pattern 3: left = mid, right = mid - 1

Use case: Rare, used in some specialized searches

Loop condition: while left < right

Why it works:

• left = mid keeps mid as potential answer
• right = mid - 1 excludes mid when it's too large
• Symmetric to Pattern 2

Template:

while left < right:
    mid = left + (right - left) // 2
    
    if condition:
        left = mid  # Keep mid
    else:
        right = mid - 1  # Exclude mid

Note: This pattern is less common. Most problems use Pattern 1 or 2.

Decision Framework

Step 1: Determine What You're Searching For

Finding exact element? → Pattern 1

• Classic binary search
• Return mid when found, -1 when not found

Finding first/last occurrence? → Pattern 2

• Lower bound (first >= target)
• Upper bound (first > target)
• Return left when loop ends

Finding insertion position? → Pattern 2

• Same as lower bound
• Return left

Step 2: Choose Loop Condition

Both pointers exclude mid? → while left <= right

• left = mid + 1 AND right = mid - 1
• Pattern 1

Either pointer keeps mid? → while left < right

• right = mid OR left = mid
• Pattern 2 or 3

Step 3: Match Initialization

Using left <= right? → right = len(arr) - 1

• Inclusive range [left, right]

Using left < right? → right = len(arr)

• Exclusive right [left, right)

Common Scenarios

Scenario 1: Find Exact Element

Problem: Find target in sorted array, return index or -1

Pattern: 1 (both exclude mid)

Code:

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

Scenario 2: Find First Occurrence

Problem: Find first occurrence of target in sorted array with duplicates

Pattern: 2 (right keeps mid)

Code:

left, right = 0, len(arr)
while left < right:
    mid = left + (right - left) // 2
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid
# Check if found
if left < len(arr) and arr[left] == target:
    return left
return -1

Scenario 3: Find Insertion Position

Problem: Find where to insert target to maintain sorted order

Pattern: 2 (same as lower bound)

Code:

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

Scenario 4: Find Last Occurrence

Problem: Find last occurrence of target

Pattern: 2 (upper bound - 1)

Code:

# Upper bound
left, right = 0, len(arr)
while left < right:
    mid = left + (right - left) // 2
    if arr[mid] <= target:
        left = mid + 1
    else:
        right = mid

# Last occurrence is upper_bound - 1
last = left - 1
if last >= 0 and arr[last] == target:
    return last
return -1

Debugging Checklist

When you get off-by-one errors, check these:

1. Pointer Updates Match Loop Condition

• Using left <= right?

  • Both pointers exclude mid? (mid + 1 and mid - 1)
• Using left < right?

  • One pointer keeps mid? (mid without ±1)

2. Initialization Matches Loop Condition

• Using left <= right?

  • right = len(arr) - 1
• Using left < right?

  • right = len(arr)

3. Return Value Is Correct

• Classic search: return mid or -1
• Lower/upper bound: return left
• Last occurrence: return upper_bound - 1

4. Edge Cases Work

Test these:

• Empty array: []
• Single element: [1]
• Target at start: [1, 2, 3], target = 1
• Target at end: [1, 2, 3], target = 3
• Target not found: [1, 2, 3], target = 4

Visual Guide: When to Use What

┌─────────────────────────────────────────────────────┐
│ Do both pointers exclude mid?                       │
│ (left = mid + 1 AND right = mid - 1)               │
└─────────────────┬───────────────────────────────────┘
                  │
         ┌────────┴────────┐
         YES              NO
         │                │
         ▼                ▼
  left <= right    left < right
  right = len-1    right = len
  Pattern 1        Pattern 2/3
  (Classic)        (Bounds)

Common Mistakes

Mistake 1: Mixing Patterns

❌ Wrong:

while left <= right:  # Pattern 1 loop condition
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid  # Pattern 2 pointer update

Fix: Match loop condition with pointer updates.

Mistake 2: Wrong Initialization

❌ Wrong:

left, right = 0, len(arr)  # Pattern 2 initialization
while left <= right:  # Pattern 1 loop condition

Fix: right = len(arr) - 1 for left <= right.

Mistake 3: Forgetting to Check Bounds

❌ Wrong:

first = lower_bound(arr, target)
return first  # Might be out of bounds!

✅ Correct:

first = lower_bound(arr, target)
if first < len(arr) and arr[first] == target:
    return first
return -1

Practice Problems

Master off-by-one errors with these:

1. Binary Search (#704) — Pattern 1
2. Search Insert Position (#35) — Pattern 2
3. First Bad Version (#278) — Pattern 2
4. Find First and Last Position (#34) — Pattern 2 (both bounds)
5. Search in Rotated Sorted Array (#33) — Pattern 1 with modifications

FAQ

Q: Why can't I use left <= right with right = mid?

A: Because you'll get an infinite loop. If left == right == mid, setting right = mid doesn't make progress.

Q: When should I use right = len(arr) vs len(arr) - 1?

A:

• len(arr) - 1: When using left <= right (inclusive range)
• len(arr): When using left < right (exclusive right)

Q: How do I remember which pattern to use?

A: Ask: "Do I need to keep mid as a potential answer?" If yes, use Pattern 2 (right = mid, left < right). If no, use Pattern 1.

Q: What if I need to find the last occurrence directly?

A: Use upper bound and subtract 1, or modify lower bound to search from right.

Conclusion

Off-by-one errors in binary search come from mismatched pointer updates and loop conditions. Master the three patterns and you'll never make these mistakes again.

Key principles:

• Pattern 1: Both exclude mid → left <= right
• Pattern 2: One keeps mid → left < right
• Match initialization with loop condition
• Test edge cases religiously

The decision tree:

1. Both pointers exclude mid? → Pattern 1
2. One pointer keeps mid? → Pattern 2
3. Match loop condition and initialization
4. Test empty, single, boundaries

Quick reference:

# Pattern 1: Classic
while left <= right:
    left = mid + 1 or right = mid - 1

# Pattern 2: Bounds
while left < right:
    left = mid + 1 and right = mid

Master these patterns, and off-by-one errors will be a thing of the past. For more details, see Implementation Mistakes, Infinite Loop Debugging, and the Complete Binary Search Guide.

Next time you write binary search, pick a pattern and stick with it. Consistency prevents bugs.