Binary Search Variations - Learning Module

Loading content...

0/276

Off-by-One Errors and How to Avoid Them

The Most Common Binary Search Bugs

Binary search is conceptually simple, yet notoriously difficult to implement correctly. In his seminal book Programming Pearls, Jon Bentley reports that in his experience, 90% of professional programmers cannot correctly implement binary search even when given pseudocode. The culprit? Off-by-one errors.

These errors are subtle. The algorithm "almost" works—it passes most test cases, seems correct in manual tracing, but fails on edge cases like:

Empty arrays
Single-element arrays
Target at the first or last position
Target not present (smaller or larger than all elements)

This page will equip you with systematic techniques to eliminate off-by-one errors from your binary search implementations—forever.

What You Will Learn

By the end of this page, you will: (1) Understand the five classic sources of off-by-one errors, (2) Master the invariant-based approach that eliminates category errors, (3) Choose correctly between < and <= loop conditions, (4) Know when to use mid - 1, mid, or mid + 1 in updates, (5) Apply a practical checklist to verify any binary search implementation.

The Five Classic Off-by-One Errors

Off-by-one errors in binary search come from just five sources. Knowing these categories helps you avoid them and debug quickly when they occur.

The Five Classic Off-by-One Errors in Binary Search
Error Type	What Goes Wrong	Example Bug	How to Avoid
Wrong initial bounds	right = len-1 when should be len, or vice versa	Can't find element at last position	Match to invariant (inclusive vs exclusive)
Wrong loop condition	< vs <= confusion	Infinite loop or missing element check	Derive from what 'left == right' means
Wrong midpoint formula	Integer overflow or wrong rounding	Crash on large arrays, or infinite loop	Use left + (right - left) / 2
Wrong pointer update	mid vs mid+1 vs mid-1 confusion	Skip elements or check same element forever	Ask: 'Can mid be the answer?'
Missing final check	Assuming loop exit means found	Return wrong index when target missing	Always verify target at final position

Let's examine each error in detail with concrete buggy code examples:

classic_bugs.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
# =====================================================
# BUG TYPE 1: Wrong initial bounds
# =====================================================
 
def binary_search_bug_1(arr, target):
    """
    BUG: right = len(arr) - 1 with the wrong loop condition.
    This combo can either miss the last element or cause other issues.
    """
    left = 0
    right = len(arr) - 1  # Inclusive right
    
    while left < right:  # BUG: Should be <= for inclusive right!
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    # MISSING: Never checked arr[left] when left == right!
    return -1
 
# Test: Target at last position
arr = [1, 2, 3, 4, 5]
print(f"Bug 1: Finding 5 in {arr}: {binary_search_bug_1(arr, 5)}")
# Returns -1, but 5 is at index 4!
 
 
# =====================================================
# BUG TYPE 2: Wrong loop condition
# =====================================================
 
def binary_search_bug_2(arr, target):
    """
    BUG: Using <= with the wrong update strategy causes infinite loop.
    """
    left = 0
    right = len(arr)  # Exclusive right
    
    while left <= right:  # BUG: Should be < for exclusive right!
        mid = (left + right) // 2
        if mid >= len(arr):  # Band-aid for the real bug
            break
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return -1
 
# This might work accidentally, but the logic is broken.
# With right = len(arr) (exclusive), left == right means 
# an empty search space, so we should stop with <, not <=.
 
 
# =====================================================
# BUG TYPE 3: Integer overflow in midpoint
# =====================================================
 
def binary_search_bug_3_concept():
    """
    BUG: mid = (left + right) // 2 overflows in languages with fixed integers.
    
    In Python, integers auto-expand, so this isn't a problem.
    In Java/C++/C#, if left + right > MAX_INT, you get overflow!
    """
    # Imagine left = 2000000000, right = 2000000001 in Java
    # left + right = 4000000001, which overflows 32-bit int!
    # Result: negative number, incorrect mid.
    
    # CORRECT: mid = left + (right - left) // 2
    # This never overflows because right - left <= right <= MAX_INT
    pass
 
 
# =====================================================
# BUG TYPE 4: Wrong pointer update
# =====================================================
 
def binary_search_bug_4(arr, target):
    """
    BUG: Using right = mid when should be right = mid - 1.
    Causes infinite loop when left + 1 == right.
    """
    left = 0
    right = len(arr) - 1  # Inclusive
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid  # BUG: Should be mid - 1 for inclusive right!
    
    return -1
 
# When left = 0, right = 1, mid = 0, and arr[0] > target:
# We set right = mid = 0. Next iteration: left = 0, right = 0, mid = 0.
# If arr[0] > target still, right = 0 again. Infinite loop!
 
 
# =====================================================
# BUG TYPE 5: Missing final check
# =====================================================
 
def binary_search_bug_5(arr, target):
    """
    BUG: Assuming the returned position contains the target.
    """
    left = 0
    right = len(arr)
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left  # BUG: Didn't check if arr[left] == target!
 
# Test: Target not in array
arr = [1, 3, 5, 7]
pos = binary_search_bug_5(arr, 4)
print(f"Bug 5: Finding 4 in {arr}: position {pos}, value {arr[pos] if pos < len(arr) else 'OOB'}")
# Returns 2 (where 5 is), but 4 isn't in the array!

These Bugs Pass Most Tests!

The insidious nature of off-by-one bugs is that they pass 95%+ of test cases. They only fail on edge cases (empty arrays, single elements, targets at boundaries). Always test these edge cases explicitly.

The Two Standard Templates

There are two correct ways to write binary search, each with its own conventions. Mixing conventions is the primary source of bugs. Choose one template and use it consistently.

Template A: Inclusive Right [left, right] Template B: Exclusive Right [left, right)

Both are correct when applied consistently. Let's see them side by side:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# TEMPLATE A: Inclusive [left, right]
def binary_search_inclusive(arr, target):
    """
    Invariant: target, if exists, is in [left, right]
    
    Key properties:
    - right = len(arr) - 1 (inclusive)
    - Loop: while left <= right
    - Update: right = mid - 1 (exclude mid)
    """
    if not arr:
        return -1
    
    left = 0
    right = len(arr) - 1  # Inclusive
    
    while left <= right:  # Both bounds included
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1  # mid excluded
    
    return -1  # target not found

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# TEMPLATE B: Exclusive [left, right)
def binary_search_exclusive(arr, target):
    """
    Invariant: target, if exists, is in [left, right)
    
    Key properties:
    - right = len(arr) (exclusive)
    - Loop: while left < right
    - Update: right = mid (mid is excluded by <)
    """
    if not arr:
        return -1
    
    left = 0
    right = len(arr)  # Exclusive
    
    while left < right:  # Stop when range empty
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid  # mid now excluded
    
    return -1  # target not found

Comparison: Inclusive vs Exclusive Templates
Property	Template A: Inclusive	Template B: Exclusive
Right initial	len(arr) - 1	len(arr)
Search space	[left, right]	[left, right)
Loop condition	left <= right	left < right
When loop exits	left > right (inverted)	left == right (empty range)
Update when >	right = mid - 1	right = mid
Update when <	left = mid + 1	left = mid + 1
Pro	Intuitive for standard search	Cleaner for boundary-finding
Con	Three-way comparison needed	Two-way comparison; may need final check

Which Template to Use?

Template A (Inclusive) is better for "find exact match" problems where you return immediately when found.

Template B (Exclusive) is better for "find boundary" problems (first/last occurrence, insertion position) because the loop naturally finds the boundary without early exit.

Most modern competitive programmers prefer Template B (exclusive) because it generalizes better to boundary problems.

The Invariant-Based Approach

The most reliable way to write correct binary search is to explicitly define and maintain a loop invariant. We've seen this in earlier pages—now let's make it a systematic technique.

The Process:

Define the invariant: What must be true about left and right at all times?
Initialize to satisfy invariant: Set left and right so the invariant holds initially.
Update to maintain invariant: Each branch must preserve the invariant.
Derive result from terminated state: What does the invariant tell us when the loop ends?

Let's apply this to the leftmost binary search:

invariant_based.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
def leftmost_binary_search_with_invariant(arr, target):
    """
    Find the first occurrence of target using explicit invariant reasoning.
    
    INVARIANT:
        - All elements at indices < left are DEFINITELY < target
        - All elements at indices >= right are DEFINITELY >= target
        - Elements in [left, right) are UNKNOWN
    
    GOAL: Find the smallest index i where arr[i] >= target
    """
    
    # STEP 1: Initialize to satisfy invariant
    # left = 0: No elements to the left, so trivially all are < target (vacuously true)
    # right = len(arr): No elements at or after, so trivially all are >= target (vacuously true)
    # Entire array is UNKNOWN - invariant satisfied.
    left = 0
    right = len(arr)
    
    # STEP 2: Loop while UNKNOWN region is non-empty
    while left < right:
        # STEP 3: Check the middle of UNKNOWN region
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            # arr[mid] is definitely < target
            # To maintain invariant: move left past mid
            # Now all indices < (mid+1) are definitely < target
            left = mid + 1
        else:  # arr[mid] >= target
            # arr[mid] is definitely >= target
            # To maintain invariant: move right to mid
            # Now all indices >= mid are definitely >= target
            right = mid
        
        # After each iteration, UNKNOWN region has shrunk by at least 1
        # Invariant is preserved.
    
    # STEP 4: Loop terminated, so left == right
    # UNKNOWN region is empty.
    # By invariant:
    #   - All indices < left are < target
    #   - All indices >= left are >= target
    # Therefore left is the first index where arr[i] >= target!
    
    # Verify target actually exists at this position
    if left < len(arr) and arr[left] == target:
        return left
    return -1
 
 
# PROVING TERMINATION:
# Each iteration, the UNKNOWN region [left, right) shrinks:
#   - If arr[mid] < target: left increases (at least by 1)
#   - If arr[mid] >= target: right decreases (at least by 1)
# 
# Initial size: right - left
# Size decreases every iteration
# Loop terminates when size = 0 (left == right)
# 
# Therefore: O(log n) iterations guaranteed.
 
 
# Test with explicit invariant checking
def leftmost_with_invariant_checks(arr, target):
    """Same algorithm but with explicit invariant assertions."""
    left = 0
    right = len(arr)
    
    iteration = 0
    while left < right:
        # Verify invariant at start of each iteration
        assert all(arr[i] < target for i in range(left)), "Left invariant violated!"
        assert all(arr[i] >= target for i in range(right, len(arr))), "Right invariant violated!"
        
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
        
        iteration += 1
        print(f"Iter {iteration}: left={left}, right={right}, unknown=[{left},{right})")
    
    print(f"Terminated: left=right={left}")
    return left if left < len(arr) and arr[left] == target else -1
 
 
# Demo
arr = [1, 2, 3, 3, 3, 3, 4, 5]
print(f"Finding first 3 in {arr}")
result = leftmost_with_invariant_checks(arr, 3)
print(f"Result: {result}")

Invariants Eliminate Guesswork

When you explicitly state the invariant, the correct update rules become derivable rather than memorizable. Ask: "What must I do to maintain the invariant?" The only answer that works IS the correct one. No more guessing between mid, mid-1, or mid+1.

Choosing the Loop Condition: < vs <=

The choice between while left < right and while left <= right is not arbitrary—it's determined by what an empty search space looks like.

The Rule:

If right is exclusive (one past last valid index): Use left < right
- Empty range: [left, right) where left == right → loop ends
If right is inclusive (last valid index): Use left <= right
- Empty range: [left, right] where left > right → loop ends

Loop Condition Based on Right Bound Convention
Convention	Right Initial	Loop Condition	Why?
Exclusive [left, right)	len(arr)	left < right	left == right means empty range
Inclusive [left, right]	len(arr) - 1	left <= right	left > right means empty range

Debugging Infinite Loops:

If your binary search runs forever, 99% of the time it's because:

You mixed conventions (exclusive right with <= condition, or inclusive with <)
Your update rules don't shrink the search space

Guaranteed Termination Check:

In every branch, ask: "Does the [left, right) or [left, right] range shrink?"

left = mid + 1 shrinks from left (✓ if mid >= left)
right = mid - 1 shrinks from right (✓ for inclusive)
right = mid shrinks from right (✓ for exclusive, because we use <)
left = mid or right = mid with the WRONG convention → infinite loop

loop_condition_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
# Analysis of when each combination works
 
# COMBINATION 1: Exclusive right + left < right ✓
def correct_exclusive():
    """
    right = len(arr) (exclusive)
    while left < right
    
    When left == right, range [left, right) is empty. Loop exits correctly.
    """
    arr = [1, 2, 3]
    left, right = 0, len(arr)  # [0, 3)
    
    iterations = 0
    while left < right:
        iterations += 1
        mid = left + (right - left) // 2
        # Simulate: always go right
        left = mid + 1
        print(f"Iter {iterations}: left={left}, right={right}")
    
    print(f"Exited after {iterations} iterations (correct)")
 
 
# COMBINATION 2: Exclusive right + left <= right ✗
def infinite_loop_example():
    """
    right = len(arr) (exclusive)
    while left <= right  ← BUG!
    
    When left == right, we're processing an empty range but don't exit!
    """
    arr = [1, 2, 3]
    left, right = 0, len(arr)  # [0, 3)
    
    iterations = 0
    while left <= right:  # BUG: Should be <
        iterations += 1
        mid = left + (right - left) // 2
        
        if iterations > 10:
            print(f"Infinite loop detected at left={left}, right={right}")
            break
        
        # When left == right == 3, mid == 3, out of bounds!
        if mid >= len(arr):
            right = mid  # This doesn't change anything!
        else:
            left = mid + 1
 
 
# COMBINATION 3: Inclusive right + left <= right ✓
def correct_inclusive():
    """
    right = len(arr) - 1 (inclusive)
    while left <= right
    
    When left > right, range [left, right] is empty. Loop exits correctly.
    """
    arr = [1, 2, 3]
    left, right = 0, len(arr) - 1  # [0, 2]
    
    iterations = 0
    while left <= right:
        iterations += 1
        mid = left + (right - left) // 2
        # Simulate: always go right
        left = mid + 1
        print(f"Iter {iterations}: left={left}, right={right}")
    
    print(f"Exited after {iterations} iterations (correct)")
 
 
# COMBINATION 4: Inclusive right + left < right ✗
def missing_element_example():
    """
    right = len(arr) - 1 (inclusive)
    while left < right  ← BUG!
    
    When left == right, we have one element but don't check it!
    """
    arr = [1, 2, 3]
    left, right = 0, len(arr) - 1  # [0, 2]
    target = 3  # At last position
    
    while left < right:  # BUG: Should be <=
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    # left == right == 2, but we never checked if arr[2] == 3!
    # Standard binary search would return -1 incorrectly
    print(f"Stopped at left={left}, right={right}")
    print(f"Never explicitly checked arr[{left}] = {arr[left]}")
 
 
print("Correct exclusive:")
correct_exclusive()
print("\nCorrect inclusive:")
correct_inclusive()
print("\nBuggy inclusive with <:")
missing_element_example()

Pointer Update Rules: mid vs mid±1

When should you use mid + 1, mid - 1, or just mid? This depends on two factors:

Your boundary convention (inclusive vs exclusive)
Whether mid could be the answer

The Golden Rule:

Exclude mid from the search space if and only if you've proven it cannot be the answer.

Pointer Update Decision Matrix
Situation	Can mid be the answer?	Inclusive right	Exclusive right
arr[mid] == target (exact match)	Yes - found it!	return mid	return mid
arr[mid] < target (too small)	No - need larger	left = mid + 1	left = mid + 1
arr[mid] > target (too large)	No - need smaller	right = mid - 1	right = mid
arr[mid] >= target (boundary search)	Maybe yes!	—	right = mid
arr[mid] <= target (boundary search)	Maybe yes!	—	left = mid + 1

Why the difference for arr[mid] > target?

Inclusive right: right points to a valid candidate. Since arr[mid] > target, mid is not a candidate. Exclude it: right = mid - 1.
Exclusive right: right points one past the last candidate. Since arr[mid] > target, mid is not a candidate. Setting right = mid makes mid the new "one past," effectively excluding it.

The boundary search case is special:

For leftmost/rightmost search, arr[mid] == target doesn't mean we're done. For leftmost, even if arr[mid] == target, there might be an earlier match. So mid could be the answer—don't exclude it. This is why we use right = mid (not mid - 1) even though arr[mid] >= target.

update_rules.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
# Demonstrating why update rules matter
 
def leftmost_CORRECT(arr, target):
    """
    Finding first occurrence.
    When arr[mid] >= target, mid MIGHT be the answer (first occurrence).
    DO NOT exclude it!
    """
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1  # mid is too small, exclude
        else:
            right = mid  # mid might be answer, DON'T exclude
    
    return left if left < len(arr) and arr[left] == target else -1
 
 
def leftmost_BUG(arr, target):
    """
    BUG: Excludes mid when we shouldn't.
    """
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1  # BUG! Might skip the first occurrence!
    
    return left if left < len(arr) and arr[left] == target else -1
 
 
# Test
arr = [1, 2, 3, 3, 3, 4]
print(f"Finding first 3 in {arr}")
print(f"CORRECT: {leftmost_CORRECT(arr, 3)}")  # 2
print(f"BUG: {leftmost_BUG(arr, 3)}")          # Likely -1 or wrong
 
 
# WHY THE BUG HAPPENS:
# When left=0, right=6, mid=3, arr[3]=3 >= 3
# We set right = mid - 1 = 2
# But arr[2]=3 is the first occurrence!
# By setting right=2 (exclusive), we now search [0, 2)
# indices 0 and 1 have values 1 and 2, neither equals 3
# We end up at left=2, right=2, but then we check arr[2]=3... 
# Actually in this case it might accidentally work. Let's try another:
 
arr2 = [1, 3, 3, 3]
print(f"\nFinding first 3 in {arr2}")
print(f"CORRECT: {leftmost_CORRECT(arr2, 3)}")  # 1
print(f"BUG: {leftmost_BUG(arr2, 3)}")          # Likely wrong
 
# With arr2:
# left=0, right=4, mid=2, arr[2]=3 >= 3, right = 1
# left=0, right=1, mid=0, arr[0]=1 < 3, left = 1
# left=1, right=1, exit loop
# arr[1]=3 == 3, returns 1 ✓
# 
# Hmm, it worked! The bug is subtle. Let's try:
 
arr3 = [3, 3, 3]
print(f"\nFinding first 3 in {arr3}")
print(f"CORRECT: {leftmost_CORRECT(arr3, 3)}")  # 0
print(f"BUG: {leftmost_BUG(arr3, 3)}")          
 
# arr3: mid=1, arr[1]=3 >= 3, right = 0
# left=0, right=0, exit
# arr[0]=3 ✓ ... still works accidentally!
 
# The bug manifests in specific cases. Let's construct one:
arr4 = [1, 2, 3]  # First 3 at index 2
print(f"\nFinding first 3 in {arr4}")
 
# CORRECT: left=0, right=3
#   mid=1, arr[1]=2 < 3, left=2
#   mid=2, arr[2]=3 >= 3, right=2
#   left==right==2, arr[2]=3 ✓
 
# BUG: left=0, right=3
#   mid=1, arr[1]=2 < 3, left=2  
#   left=2, right=3, mid=2, arr[2]=3 >= 3, right=1  ← BUG!
#   left=2, right=1, left > right... hmm, with exclusive this is invalid state
#   Actually left < right fails (2 < 1 is false), so we exit with left=2
#   But we skipped the element!
 
# The key insight: with exclusive right and right = mid - 1,
# we're mixing conventions. That's the root cause.

Simple Rule of Thumb

For Template B (exclusive right):

Always use left = mid + 1 when moving left
Always use right = mid when moving right

For Template A (inclusive right):

Always use left = mid + 1 when moving left
Always use right = mid - 1 when moving right

Never mix and match!

The Midpoint Formula: Avoiding Overflow

A subtle but important source of bugs is integer overflow when computing the midpoint. This is a problem in languages like Java, C++, and C# where integers have fixed size.

The Problem:

int mid = (left + right) / 2;  // BUG: left + right might overflow!

If left = 2,000,000,000 and right = 2,000,000,001, then left + right = 4,000,000,001, which exceeds the maximum 32-bit signed integer (2,147,483,647). The result wraps around to a negative number, giving an incorrect (and likely negative) midpoint.

The Solution:

int mid = left + (right - left) / 2;  // CORRECT: never overflows

right - left is always ≤ right, which fits in an int. Adding it to left also stays within bounds.

Midpoint Formulas
Formula	Safe?	Notes
(left + right) / 2	No	Overflows when left + right > MAX_INT
left + (right - left) / 2	Yes	Standard safe formula
(left + right) >>> 1 (Java)	Yes	Unsigned right shift; treats result as positive
left + ((right - left) >> 1)	Yes	Equivalent to division by 2 for non-negative

Additional Considerations:

Python doesn't overflow: Python integers are arbitrary precision, so (left + right) // 2 is fine. But use the safe formula anyway for consistency if you work in multiple languages.
Rounding direction: left + (right - left) // 2 rounds down (toward left). This matters for some algorithms. To round up: left + (right - left + 1) // 2.
Off-by-one from rounding: When left and right are adjacent (differ by 1), mid always equals left with floor division. This is why left = mid causes infinite loops—if left doesn't change, neither does mid.

midpoint_analysis.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
# Demonstrating midpoint calculations
 
def analyze_midpoint():
    """Show how midpoint behaves in edge cases."""
    
    test_cases = [
        (0, 10),    # Normal case
        (0, 1),     # Adjacent (critical for loop termination)
        (5, 5),     # Same (should this even happen?)
        (0, 0),     # Degenerate
        (10, 11),   # Adjacent at higher values
    ]
    
    for left, right in test_cases:
        mid_floor = left + (right - left) // 2
        mid_ceil = left + (right - left + 1) // 2
        print(f"[{left}, {right}]: mid_floor={mid_floor}, mid_ceil={mid_ceil}")
 
 
analyze_midpoint()
 
# Output:
# [0, 10]: mid_floor=5, mid_ceil=5
# [0, 1]: mid_floor=0, mid_ceil=1    ← Important!
# [5, 5]: mid_floor=5, mid_ceil=5
# [0, 0]: mid_floor=0, mid_ceil=0
# [10, 11]: mid_floor=10, mid_ceil=11
 
 
# Why floor vs ceil matters:
# With floor: mid = left when left + 1 == right
# If we update left = mid, we get left = left → infinite loop!
# 
# With ceil: mid = right when left + 1 == right  
# If we update right = mid, we get right = right → infinite loop!
#
# The solution: never use "left = mid" with floor, never use "right = mid" with ceil.
# Standard convention (floor) requires left = mid + 1, right = mid.
 
 
# Demonstrating the infinite loop trap
def infinite_loop_demo():
    """
    Shows how left = mid causes infinite loop with floor midpoint.
    """
    left, right = 0, 2
    iterations = 0
    
    while left < right:
        mid = left + (right - left) // 2  # Floor
        print(f"Iter {iterations}: left={left}, right={right}, mid={mid}")
        
        # Simulating "left = mid" update (BUG!)
        if iterations == 0:
            right = mid  # First: right becomes 1
        else:
            left = mid   # Then: left stays 0 forever!
        
        iterations += 1
        if iterations > 5:
            print("Infinite loop detected!")
            break
 
 
print("\nInfinite loop demo:")
infinite_loop_demo()

The Binary Search Verification Checklist

Use this checklist every time you write binary search. If you can answer "yes" to all items, your implementation is correct.

Binary Search Verification Checklist

•Bounds are consistent: Am I using inclusive [left, right] or exclusive [left, right)? Is this consistent throughout?
•Loop condition matches bounds: Am I using <= for inclusive or < for exclusive?
•Midpoint is overflow-safe: Am I using left + (right - left) // 2 instead of (left + right) // 2?
•Every branch shrinks the range: Does left increase or right decrease in every case?
•No infinite loop possible: For adjacent left/right, does the loop still terminate?
•Checked empty array: Does my code handle arr = [] correctly?
•Checked single element: Does my code handle arr = [x] for target equal to x and not equal to x?
•Checked target at boundaries: Does it work when target is at index 0? At index len-1?
•Checked target not present: Does it work when target is less than all elements? Greater than all?
•Final result is verified: If returning an index, do I check that arr[index] == target?

comprehensive_test.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def verify_binary_search(search_fn, description=""):
    """
    Comprehensive test suite for any binary search implementation.
    Tests all edge cases from the checklist.
    """
    print(f"Testing: {description or search_fn.__name__}")
    
    test_cases = [
        # (array, target, expected, description)
        ([], 5, -1, "Empty array"),
        ([5], 5, 0, "Single element - found"),
        ([5], 3, -1, "Single element - target smaller"),
        ([5], 7, -1, "Single element - target larger"),
        ([1, 2, 3, 4, 5], 1, 0, "Target at start"),
        ([1, 2, 3, 4, 5], 5, 4, "Target at end"),
        ([1, 2, 3, 4, 5], 3, 2, "Target in middle"),
        ([1, 2, 3, 4, 5], 0, -1, "Target smaller than all"),
        ([1, 2, 3, 4, 5], 6, -1, "Target larger than all"),
        ([1, 2, 4, 5], 3, -1, "Target missing (gap in middle)"),
        ([1, 3], 2, -1, "Target missing (two elements)"),
        ([1, 1, 1, 1], 1, "any", "All same - should find some index"),
        (list(range(1000)), 0, 0, "Large array - target at start"),
        (list(range(1000)), 999, 999, "Large array - target at end"),
        (list(range(1000)), 500, 500, "Large array - target in middle"),
        (list(range(1000)), 1000, -1, "Large array - target missing"),
    ]
    
    passed = 0
    failed = 0
    
    for arr, target, expected, desc in test_cases:
        result = search_fn(arr, target)
        
        # Handle "any" expected value for duplicate arrays
        if expected == "any":
            if 0 <= result < len(arr) and arr[result] == target:
                passed += 1
                print(f"  ✓ {desc}")
            else:
                failed += 1
                print(f"  ✗ {desc}: expected valid index, got {result}")
        elif result == expected:
            passed += 1
            print(f"  ✓ {desc}")
        else:
            failed += 1
            print(f"  ✗ {desc}: expected {expected}, got {result}")
    
    print(f"\nResult: {passed}/{passed + failed} passed\n")
    return failed == 0
 
 
# Test a correct implementation
def correct_binary_search(arr, target):
    if not arr:
        return -1
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return -1
 
 
verify_binary_search(correct_binary_search, "Correct Implementation")

Summary: Eliminating Off-by-One Errors

Off-by-one errors in binary search are preventable with systematic techniques. By understanding the sources of bugs and applying disciplined verification, you can write correct binary search every time.

Key Takeaways

•Five sources of bugs: Wrong bounds, wrong condition, overflow, wrong update, missing check. Know them all.
•Choose one template: Either inclusive [left, right] with <=, or exclusive [left, right) with <. Never mix.
•Use invariants: Explicitly define what left and right mean. Derive updates from maintaining the invariant.
•Match condition to bounds: <= for inclusive, < for exclusive. This is non-negotiable.
•Update safely: For exclusive right, use left = mid + 1 and right = mid. For inclusive, use mid ± 1.
•Safe midpoint formula: Always use left + (right - left) // 2 to avoid overflow.
•Test edge cases: Empty, single, boundaries, missing. These catch 90% of bugs.

Quick Reference: Correct Binary Search Patterns
Template	Initial right	Loop	Update when >	Update when <
Exclusive (recommended)	len(arr)	left < right	right = mid	left = mid + 1
Inclusive	len(arr) - 1	left <= right	right = mid - 1	left = mid + 1

Module Complete:

You've now mastered the complete spectrum of binary search variations and edge cases. From finding first and last occurrences, to handling duplicates, to avoiding the notorious off-by-one errors—you have the tools to implement binary search correctly in any context.

The next module will explore Binary Search on Answer Space, where we apply binary search not to find elements in an array, but to find optimal values that satisfy certain conditions. This powerful technique appears in many optimization and decision problems.

Module Complete

Congratulations! You've completed the Binary Search Variations & Edge Cases module. You now understand leftmost/rightmost search, insertion positions, duplicate handling, and off-by-one error prevention. These are the skills that separate correct binary search implementations from buggy ones.