LeetCopilot Logo
LeetCopilot
LeetCode Pattern/Binary Search/Lower Bound vs Upper Bound in Binary Search: Common Mistakes and Fixes

Lower Bound vs Upper Bound in Binary Search: Common Mistakes and Fixes

LeetCopilot Team
Dec 30, 2025
6 min read
Binary SearchLower BoundUpper BoundCommon MistakesTemplates
Stop confusing lower bound and upper bound. Learn the exact difference, common mistakes (wrong pointer, wrong condition), and how to remember which is which.
Complete Guide

The Complete Binary Search Guide: Master All Patterns, Templates, and Techniques

The ultimate comprehensive guide to binary search. Learn all variants (classic, binary search on answer, rotated arrays), when to use each pattern, complete templates in multiple languages, and a systematic approach to solve any binary search problem.

Read the complete guide

Lower bound and upper bound look almost identical, but one character difference (< vs <=) changes everything. Confusing them leads to wrong answers on "find first/last occurrence" problems.

This guide shows the exact difference, common mistakes, and a simple way to remember which is which.

TL;DR

Lower bound: First element >= target

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

Upper bound: First element > target

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

The only difference: < vs <=

Definitions

Lower Bound

First position where element >= target

code
Array: [1, 2, 2, 2, 3, 4]
        0  1  2  3  4  5

lower_bound(2) = 1  (first 2)
lower_bound(2.5) = 4  (first element >= 2.5 is 3)

Upper Bound

First position where element > target

code
Array: [1, 2, 2, 2, 3, 4]
        0  1  2  3  4  5

upper_bound(2) = 4  (first element > 2 is 3)
upper_bound(2.5) = 4  (first element > 2.5 is 3)

Visual Comparison

code
Array: [1, 2, 2, 2, 3, 4]
           ↑        ↑
        lower(2) upper(2)
    
lower_bound(2) = 1  (first >= 2)
upper_bound(2) = 4  (first > 2)

Last occurrence of 2 = upper_bound(2) - 1 = 3

Common Mistake 1: Returning Wrong Pointer

The Problem

Returning mid instead of left after the loop.

❌ Wrong:

python
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 mid  # WRONG: mid is not defined after loop

✅ Correct:

python
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  # Correct: left == right when loop ends

Common Mistake 2: Wrong Pointer Update

The Problem

Using right = mid - 1 instead of right = mid.

❌ Wrong:

python
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 - 1  # WRONG: excludes potential answer
    return left

Why it's wrong: arr[mid] might be the first occurrence. We can't exclude it.

✅ Correct:

python
right = mid  # Keep mid as potential answer

Common Mistake 3: Confusing the Two

The Problem

Using lower bound template for upper bound (or vice versa).

❌ Wrong (using lower bound for upper bound):

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

✅ Correct:

python
if arr[mid] <= target:  # Correct: exclude elements <= target
    left = mid + 1

Side-by-Side Template Comparison

Lower Bound

python
def lower_bound(arr, target):
    """First element >= target"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] < target:  # Exclude elements < target
            left = mid + 1
        else:  # arr[mid] >= target
            right = mid  # Keep as potential answer
    
    return left

Upper Bound

python
def upper_bound(arr, target):
    """First element > target"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] <= target:  # Exclude elements <= target
            left = mid + 1
        else:  # arr[mid] > target
            right = mid  # Keep as potential answer
    
    return left

The only difference: Line 7: < vs <=

How to Remember

Mnemonic 1: "Equal Sign"

  • Lower bound: < (no equal) → keeps elements = target
  • Upper bound: <= (has equal) → excludes elements = target

Mnemonic 2: "What We're Finding"

  • Lower bound: First >= target → exclude < target
  • Upper bound: First > target → exclude <= target

Mnemonic 3: "Condition Matches Goal"

  • Lower bound: Find >= → exclude <
  • Upper bound: Find > → exclude <=

Finding First and Last Occurrence

Using Both Bounds

python
def find_first_last(arr, target):
    # First occurrence = lower_bound
    first = lower_bound(arr, target)
    
    # Check if target exists
    if first == len(arr) or arr[first] != target:
        return [-1, -1]
    
    # Last occurrence = upper_bound - 1
    last = upper_bound(arr, target) - 1
    
    return [first, last]

# Example
arr = [5, 7, 7, 8, 8, 10]
print(find_first_last(arr, 8))  # [3, 4]

Why This Works

code
Array: [5, 7, 7, 8, 8, 10]
        0  1  2  3  4  5

Target = 8:
  lower_bound(8) = 3  (first >= 8)
  upper_bound(8) = 5  (first > 8)
  last occurrence = 5 - 1 = 4 ✓

Practice Examples

Example 1: Find First Occurrence

python
arr = [1, 2, 2, 2, 3, 4]
target = 2

lower_bound(arr, 2) = 1  # First 2 at index 1 ✓

Example 2: Find Last Occurrence

python
arr = [1, 2, 2, 2, 3, 4]
target = 2

upper_bound(arr, 2) = 4  # First > 2 at index 4
last = 4 - 1 = 3  # Last 2 at index 3 ✓

Example 3: Target Doesn't Exist

python
arr = [1, 2, 4, 5]
target = 3

lower_bound(arr, 3) = 2  # Would insert at index 2
upper_bound(arr, 3) = 2  # Same

Debugging Checklist

When your bounds are wrong:

  • Using < for lower bound, <= for upper bound?
  • Returning left (not mid)?
  • Using right = mid (not mid - 1)?
  • Initializing right = len(arr) (not len(arr) - 1)?
  • Using left < right (not left <= right)?

FAQ

Q: Why is it called "lower bound" and "upper bound"?

A: Lower bound is the lower boundary of where target could be (first >=). Upper bound is the upper boundary (first >).

Q: Can I use these on unsorted arrays?

A: No. Like all binary search, they require sorted data.

Q: What if target is larger than all elements?

A: Both return len(arr) (insertion position at end).

Q: What if target is smaller than all elements?

A: Both return 0 (insertion position at start).

Q: How do I find the count of target?

A: count = upper_bound(target) - lower_bound(target)

Conclusion

Lower bound and upper bound differ by one character, but that character matters.

Key differences:

  • Lower bound: First >= target, exclude < target
  • Upper bound: First > target, exclude <= target
  • Code difference: < vs <=

Common mistakes:

  • Returning mid instead of left
  • Using right = mid - 1 instead of right = mid
  • Confusing which condition to use

How to remember:

  • Lower bound: < (no equal)
  • Upper bound: <= (has equal)

Finding occurrences:

  • First = lower_bound
  • Last = upper_bound - 1
  • Count = upper_bound - lower_bound

Master these two templates and you'll handle duplicates with confidence. For more details, see Find First and Last Position Template and the Complete Binary Search Guide.

Want to Practice LeetCode Smarter?

LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.

Learn More About LeetCopilot
ChromeAdd to Chrome for free

Also compatible with Edge, Brave, and Opera

Related Tutorials