Finding the first or last occurrence of an element in a sorted array with duplicates is one of the most common binary search variations. It's used in dozens of LeetCode problems, appears frequently in interviews, and forms the foundation for more advanced binary search techniques.
But here's the challenge: the pointer update logic is subtle. Using left = mid + 1 vs left = mid, or right = mid - 1 vs right = mid, makes the difference between a correct solution and an infinite loop or wrong answer.
This comprehensive guide will teach you the exact templates for lower bound and upper bound, when to use each, how they differ from classic binary search, and how to avoid the mistakes that cause bugs.
Lower bound: First position where element >= target (or insertion position)
Upper bound: First position where element > target
Lower bound template:
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return leftUpper bound template:
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return leftKey difference: < vs <= in the condition
Lower bound (first occurrence):
The first position where the element is greater than or equal to the target.
Upper bound (last occurrence):
The first position where the element is greater than the target.
Visual examples:
Array: [1, 2, 2, 2, 3, 4, 5]
0 1 2 3 4 5 6
Target = 2:
Lower bound: 1 (first occurrence of 2)
Upper bound: 4 (first element > 2, which is 3)
Target = 2.5 (doesn't exist):
Lower bound: 4 (where 2.5 would be inserted)
Upper bound: 4 (same)
Target = 0 (less than all):
Lower bound: 0
Upper bound: 0
Target = 10 (greater than all):
Lower bound: 7 (len(arr))
Upper bound: 7Standard binary search:
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 # Returns ANY occurrence
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Problem with duplicates:
Array: [1, 2, 2, 2, 3]
Target: 2
Standard binary search might return index 1, 2, or 3
We don't know which occurrence we'll get!Solution: Use lower/upper bound to find specific occurrences.
def lower_bound(arr, target):
"""
Find first position where arr[i] >= target
Time: O(log n)
Space: O(1)
Returns: Index of first element >= target, or len(arr) if all < target
"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
# arr[mid] is too small, answer is in right half
left = mid + 1
else:
# arr[mid] >= target, could be the answer
# Keep searching left for earlier occurrence
right = mid
return leftfunction lowerBound(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}public int lowerBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}Key insights:
right = len(arr) (not len(arr) - 1)left < right (not left <= right)left = mid + 1 when arr[mid] < targetright = mid when arr[mid] >= target (not mid - 1)left (which equals right when loop ends)Why right = mid instead of right = mid - 1?
Because arr[mid] might be the answer! If arr[mid] >= target, we can't exclude it.
Step-by-step trace:
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 of 2) ✓def upper_bound(arr, target):
"""
Find first position where arr[i] > target
Time: O(log n)
Space: O(1)
Returns: Index of first element > target, or len(arr) if all <= target
"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
# arr[mid] is too small or equal, answer is in right half
left = mid + 1
else:
# arr[mid] > target, could be the answer
right = mid
return leftfunction upperBound(arr, target) {
let left = 0;
let right = arr.length;
while (left < right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}public int upperBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}The only difference from lower bound: <= instead of <
Why this works:
>= target → exclude elements < target> target → exclude elements <= targetStep-by-step trace:
Array: [1, 2, 2, 2, 3], target = 2
left=0, right=5, mid=2
arr[2]=2 <= 2 → left=3
left=3, right=5, mid=4
arr[4]=3 > 2 → right=4
left=3, right=4, mid=3
arr[3]=2 <= 2 → left=4
left=4, right=4 → stop
Return 4 (first element > 2, which is 3) ✓Problem statement: Find the starting and ending position of a target value in a sorted array.
Solution:
def searchRange(nums: List[int], target: int) -> List[int]:
"""
Find first and last position of target
Time: O(log n)
Space: O(1)
"""
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
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
# Find first occurrence
first = lower_bound(nums, target)
# Check if target exists
if first == len(nums) or nums[first] != target:
return [-1, -1]
# Find last occurrence (upper_bound - 1)
last = upper_bound(nums, target) - 1
return [first, last]
# Examples
print(searchRange([5, 7, 7, 8, 8, 10], 8)) # [3, 4]
print(searchRange([5, 7, 7, 8, 8, 10], 6)) # [-1, -1]
print(searchRange([], 0)) # [-1, -1]Why it works:
Step-by-step walkthrough:
Array: [5, 7, 7, 8, 8, 10], target = 8
Lower bound (first occurrence):
left=0, right=6, mid=3 → arr[3]=8 >= 8 → right=3
left=0, right=3, mid=1 → arr[1]=7 < 8 → left=2
left=2, right=3, mid=2 → arr[2]=7 < 8 → left=3
left=3, right=3 → return 3 ✓
Upper bound (after last occurrence):
left=0, right=6, mid=3 → arr[3]=8 <= 8 → left=4
left=4, right=6, mid=5 → arr[5]=10 > 8 → right=5
left=4, right=5, mid=4 → arr[4]=8 <= 8 → left=5
left=5, right=5 → return 5
Last occurrence = 5 - 1 = 4 ✓
Answer: [3, 4]1. Target doesn't exist:
searchRange([1, 2, 3], 4) # [-1, -1]
# lower_bound returns 3 (len(arr)), check fails2. Single occurrence:
searchRange([1, 2, 3], 2) # [1, 1]
# lower_bound = 1, upper_bound = 2, last = 2 - 1 = 13. All elements are target:
searchRange([2, 2, 2], 2) # [0, 2]
# lower_bound = 0, upper_bound = 3, last = 3 - 1 = 24. Empty array:
searchRange([], 1) # [-1, -1]
# lower_bound returns 0, check fails (0 == len([]))Problem statement: You are a product manager and have n versions [1, 2, ..., n]. Find the first bad version.
Solution:
def firstBadVersion(n: int) -> int:
"""
Find first bad version (lower bound problem)
Time: O(log n)
Space: O(1)
"""
left, right = 1, n + 1
while left < right:
mid = left + (right - left) // 2
if not isBadVersion(mid):
# mid is good, first bad is in right half
left = mid + 1
else:
# mid is bad, could be the first bad
right = mid
return left
# Example
# Versions: [G, G, G, B, B, B]
# 1 2 3 4 5 6
# Answer: 4 (first bad version)Why this is a lower bound problem:
isBadVersion(x) == TrueComparison to array lower bound:
Array: [0, 0, 0, 1, 1, 1] (0=good, 1=bad)
Versions: [G, G, G, B, B, B]
Lower bound for target=1 → index 3 (first bad version)❌ Wrong:
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: should be mid
return leftProblem: right = mid - 1 excludes the potential answer at mid.
✅ Correct:
right = mid # Keep mid as potential answerSee guide: Lower Bound vs Upper Bound Mistakes
❌ Wrong:
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:
return left # left == right when loop ends❌ Wrong:
# Finding last occurrence
last = upper_bound(nums, target) # WRONG: should be - 1✅ Correct:
last = upper_bound(nums, target) - 1 # Upper bound is AFTER last occurrence❌ Wrong:
left, right = 0, len(arr) - 1 # WRONG for lower/upper bound✅ Correct:
left, right = 0, len(arr) # Right is exclusiveWhy: With right = len(arr), we can return len(arr) when all elements are less than target.
| Aspect | Lower Bound | Upper Bound |
|---|---|---|
| Definition | First element >= target | First element > target |
| Condition | arr[mid] < target | arr[mid] <= target |
| Use case | First occurrence, insertion position | After last occurrence |
| Target exists | Index of first occurrence | Index after last occurrence |
| Target missing | Insertion position | Same as lower bound |
Visual comparison:
Array: [1, 2, 2, 2, 3, 4]
0 1 2 3 4 5
Target = 2:
Lower bound: 1 (first 2)
Upper bound: 4 (first element > 2, which is 3)
Last occurrence: upper_bound - 1 = 3
Target = 2.5:
Lower bound: 4 (where 2.5 would go)
Upper bound: 4 (same)Code comparison:
# Lower bound
if arr[mid] < target: # Exclude elements < target
left = mid + 1
else: # Keep elements >= target
right = mid
# Upper bound
if arr[mid] <= target: # Exclude elements <= target
left = mid + 1
else: # Keep elements > target
right = midMaster lower and upper bounds with these problems:
Beginner:
Intermediate:
4. Find First and Last Position (#34) — Both bounds
5. Count of Range Sum (#327) — Using bounds for counting
6. Find K Closest Elements (#658) — Lower bound + sliding window
Advanced:
7. Count of Smaller Numbers After Self (#315) — Binary search + merge sort
8. Russian Doll Envelopes (#354) — Lower bound + LIS
Q: When should I use lower bound vs upper bound?
A:
Q: Why right = len(arr) instead of len(arr) - 1?
A: So we can return len(arr) when all elements are less than target. This represents the insertion position at the end.
Q: Can I use left <= right instead of left < right?
A: No. With left < right, when the loop ends, left == right is the answer. With left <= right, you need different pointer updates and return logic.
Q: How do I find the last occurrence directly?
A: Use upper bound and subtract 1:
last = upper_bound(arr, target) - 1
if last >= 0 and arr[last] == target:
return last # Last occurrenceQ: What if I need to find elements in a range [L, R]?
A: Use both bounds:
left_idx = lower_bound(arr, L)
right_idx = upper_bound(arr, R)
count = right_idx - left_idxLower bound and upper bound are essential binary search variants that handle duplicates correctly. They form the foundation for many advanced algorithms and are frequently tested in interviews.
Key principles:
right = mid (not mid - 1) to keep potential answerleft < right (not left <= right)right = len(arr) (not len(arr) - 1)The templates:
# Lower bound
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
# Upper bound
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return leftWhen to use:
Master these templates, and you'll handle duplicates with confidence. For more patterns, see the Complete Binary Search Guide, Off-by-One Errors, and Implementation Mistakes.
Next time you see duplicates in a sorted array, reach for lower or upper bound.
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.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free