7 Binary Search Implementation Mistakes That Cause Infinite Loops and Wrong Answers

Binary search is conceptually simple: divide and conquer. But implementation? That's where most developers struggle.

You understand the algorithm. You know it should be O(log n). But your code either returns wrong answers, gets stuck in infinite loops, or fails edge cases. These bugs are frustrating because they're subtle—a single character difference (< vs <=, mid vs mid + 1) changes everything.

This comprehensive guide covers the 7 most common binary search implementation mistakes, why they happen, how to fix them, and debugging checklists to prevent them.

TL;DR

The 7 deadly mistakes:

1. Integer overflow in mid calculation
2. Infinite loops from wrong pointer updates
3. Off-by-one in boundary initialization
4. Wrong loop condition (< vs <=)
5. Returning wrong value (mid vs left vs right)
6. Not handling edge cases (empty array, single element)
7. Using binary search on unsorted data

Quick fixes:

• Use mid = left + (right - left) // 2
• Ensure pointer updates make progress
• Match loop condition with pointer updates
• Handle edge cases first

Mistake 1: Wrong Mid Calculation (Integer Overflow)

The Problem

❌ Wrong:

mid = (left + right) // 2

Why it's wrong: In languages like Java, C++, or JavaScript (with large numbers), left + right can overflow.

Example:

int left = 2000000000;
int right = 2000000000;
int mid = (left + right) / 2;  // Overflow! Becomes negative

The Fix

✅ Correct:

mid = left + (right - left) // 2

Why it works:

• right - left is always within valid range
• Adding to left keeps result within bounds
• Mathematically equivalent to (left + right) // 2

Language-specific notes:

Python: No integer overflow, but use correct form for consistency

mid = left + (right - left) // 2

JavaScript: Use Math.floor for integer division

const mid = left + Math.floor((right - left) / 2);

Java/C++: Critical to avoid overflow

int mid = left + (right - left) / 2;

Why It Matters

Problem size: Arrays with 2 billion elements
Consequence: Negative mid → array index out of bounds → crash

Real interview scenario:

Interviewer: "What if the array has 2 billion elements?"
You: "I use mid = left + (right - left) / 2 to prevent overflow."
Interviewer: ✓ (Shows attention to detail)

Mistake 2: Infinite Loop (Wrong Pointer Updates)

The Problem

❌ Wrong:

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  # WRONG: can cause infinite loop
        else:
            right = mid - 1
    
    return -1

Why it causes infinite loop:

Array: [1, 2], target = 2

left=0, right=1, mid=0
  arr[0]=1 < 2 → left=0 (no progress!)
  
left=0, right=1, mid=0
  arr[0]=1 < 2 → left=0 (stuck!)
  
Infinite loop!

The Fix

✅ Correct:

if arr[mid] < target:
    left = mid + 1  # Always make progress
else:
    right = mid - 1

Rule: Pointer updates must always make progress (exclude mid from next search).

The Three Safe Patterns

Pattern 1: Classic binary search

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

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

Pattern 3: Upper bound

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

Key insight: If you use right = mid, you MUST use left < right (not <=).

See detailed guide: Infinite Loop Debugging

Mistake 3: Off-by-One in Boundaries

The Problem

❌ Wrong:

# Initialization
left, right = 0, len(arr)  # right is out of bounds!

# Or
left, right = 1, len(arr) - 1  # Excludes first/last element

The Fix

✅ Correct (Classic binary search):

left, right = 0, len(arr) - 1  # Inclusive range [left, right]
while left <= right:
    ...

✅ Correct (Lower/upper bound):

left, right = 0, len(arr)  # Exclusive right [left, right)
while left < right:
    ...

The Two Conventions

Convention 1: Inclusive range [left, right]

• right = len(arr) - 1
• while left <= right
• left = mid + 1, right = mid - 1

Convention 2: Exclusive right [left, right)

• right = len(arr)
• while left < right
• left = mid + 1, right = mid

Rule: Pick one convention and stick with it. Mixing causes bugs.

See detailed guide: Off-by-One Errors in Binary Search

Mistake 4: Wrong Loop Condition

The Problem

❌ Wrong:

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

Why it's wrong: With right = mid, left can equal right, causing infinite loop or wrong answer.

The Fix

Decision table:

Rule: If either pointer is set to mid (not mid ± 1), use left < right.

Examples:

✅ Classic binary search:

while left <= right:  # Both pointers exclude mid
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

✅ Lower bound:

while left < right:  # right = mid keeps mid
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid

Mistake 5: Returning Wrong Value

The Problem

❌ Wrong:

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
        else:
            right = mid - 1
    
    return mid  # WRONG: mid is not defined after loop

The Fix

Classic binary search: Return -1 (not found)

while left <= right:
    ...
return -1  # Target not found

Lower/upper bound: Return left (or right, they're equal)

while left < right:
    ...
return left  # Insertion position or first occurrence

Search insert position: Return left

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

When to Return What

Mistake 6: Not Handling Edge Cases

The Problem

❌ Wrong:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1  # Crashes if arr is empty!
    
    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

The Fix

✅ Correct:

def binary_search(arr, target):
    # Handle edge cases first
    if not arr:
        return -1
    
    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

Edge Cases Checklist

Always test:

1. Empty array: []
2. Single element: [1]
   • Target found: target = 1
   • Target not found: target = 2
3. Two elements: [1, 2]
   • Target at start: target = 1
   • Target at end: target = 2
   • Target not found: target = 3
4. Target at boundaries:
   • First element
   • Last element
5. Target not in array:
   • Less than all elements
   • Greater than all elements
   • Between elements

Example tests:

# Empty
assert binary_search([], 1) == -1

# Single element
assert binary_search([1], 1) == 0
assert binary_search([1], 2) == -1

# Two elements
assert binary_search([1, 2], 1) == 0
assert binary_search([1, 2], 2) == 1
assert binary_search([1, 2], 3) == -1

# Boundaries
assert binary_search([1, 2, 3, 4, 5], 1) == 0
assert binary_search([1, 2, 3, 4, 5], 5) == 4

# Not found
assert binary_search([1, 2, 3, 4, 5], 0) == -1
assert binary_search([1, 2, 3, 4, 5], 6) == -1

Mistake 7: Using Binary Search on Unsorted Data

The Problem

❌ Wrong:

def two_sum(nums, target):
    # nums is UNSORTED!
    left, right = 0, len(nums) - 1
    
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # WRONG: doesn't work on unsorted data
        else:
            right -= 1
    
    return []

Why it fails:

Array: [3, 2, 4], target = 6

left=0, right=2
  3 + 4 = 7 > 6 → right=1

left=0, right=1
  3 + 2 = 5 < 6 → left=1

left=1, right=1 → stop
Missed the answer [1, 2] (2 + 4 = 6)!

The Fix

Option 1: Sort first (if indices don't matter)

def three_sum(nums):
    nums.sort()  # Now binary search works
    # ... use two pointers

Option 2: Use hash map (if need original indices)

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Rule: Binary search requires sorted data or monotonic property.

See guide: Why Binary Search Requires Sorted Data

Debugging Checklist

When your binary search fails, check these in order:

1. Mid Calculation

• Using mid = left + (right - left) // 2?
• Not using mid = (left + right) // 2?

2. Pointer Updates

• Do pointer updates always make progress?
• If left = mid, is right = mid - 1?
• If right = mid, is left = mid + 1?

3. Loop Condition

• Using left <= right with left = mid + 1, right = mid - 1?
• Using left < right with right = mid or left = mid?

4. Initialization

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

5. Return Value

• Returning correct value for problem type?
• Classic search: mid or -1
• Lower/upper bound: left

6. Edge Cases

• Handling empty array?
• Handling single element?
• Testing boundaries?

7. Data Assumption

• Is array actually sorted?
• Does monotonic property hold?

Quick Reference: The Three Templates

Template 1: Classic Binary Search

def binary_search(arr, target):
    if not arr:
        return -1
    
    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

Template 2: 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
        else:
            right = mid
    
    return left

Template 3: Upper Bound

def upper_bound(arr, target):
    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

Practice Strategy

Step 1: Memorize the three templates above

Step 2: Solve these problems to internalize patterns

1. Binary Search (#704) — Classic
2. Search Insert Position (#35) — Lower bound
3. First Bad Version (#278) — Lower bound
4. Find First and Last Position (#34) — Both bounds

Step 3: Debug intentionally broken code

• Change < to <= and see what breaks
• Use left = mid instead of left = mid + 1
• Try right = len(arr) with left <= right

Step 4: Test all edge cases for every solution

FAQ

Q: How do I remember which loop condition to use?

A: If you set either pointer to mid (not mid ± 1), use left < right. Otherwise use left <= right.

Q: Why does my binary search work on examples but fail on edge cases?

A: You're not testing empty arrays, single elements, or boundary values. Always test the edge cases checklist.

Q: My code works in Python but fails in Java. Why?

A: Integer overflow. Use mid = left + (right - left) / 2 in Java.

Q: How do I know if I should return left, right, or mid?

A:

• Classic search (found): return mid
• Classic search (not found): return -1
• Lower/upper bound: return left (equals right when loop ends)

Q: Can I use recursion instead of iteration?

A: Yes, but iteration is preferred (O(1) space vs O(log n) space). Recursion has the same pitfalls.

Conclusion

Binary search implementation is deceptively tricky. Seven common mistakes account for 90% of bugs:

1. Integer overflow → Use mid = left + (right - left) // 2
2. Infinite loops → Ensure pointer updates make progress
3. Off-by-one → Match initialization with loop condition
4. Wrong loop condition → Use < if pointer set to mid
5. Wrong return value → Return left for bounds, mid or -1 for classic
6. Missing edge cases → Test empty, single, boundaries
7. Unsorted data → Verify sorted property or use hash map

The debugging checklist:

1. Check mid calculation
2. Verify pointer updates make progress
3. Match loop condition with pointer updates
4. Test edge cases
5. Confirm data is sorted

Master the three templates:

• Classic: left <= right, exclude mid from both sides
• Lower bound: left < right, right = mid
• Upper bound: left < right, right = mid, <= condition

Practice deliberately, test edge cases religiously, and you'll never submit a buggy binary search again. For more details, see Off-by-One Errors, Infinite Loop Debugging, and the Complete Binary Search Guide.

Next time your binary search fails, run through the checklist. The bug is always one of these seven.