Data Structures & AlgorithmsBinary Search Variations & Edge Cases

Binary Search Variations & Edge Cases

LevelIntermediate

Duration90 mins

TopicBinary Search Variations & Edge Cases

2 / 5

Finding Last Occurrence

The Symmetric Challenge

In the previous page, we mastered leftmost binary search—finding the first occurrence of a target in a sorted array. Now we tackle its symmetric counterpart: rightmost binary search (also called upper bound search).

At first glance, this might seem trivially similar. Just "search from the right," right? But the devil is in the details. A naive approach leads to subtle bugs, and understanding the precise relationship between leftmost and rightmost search unlocks powerful range-based algorithms.

Real-World Motivations:

"What was the last day our inventory fell below the reorder threshold?"
"Find the rightmost index where a target appears."
"How many elements are less than or equal to a threshold?"
"What is the range [first, last] of all occurrences of a value?"

This page will equip you with a complete understanding of rightmost binary search, its relationship to leftmost search, and how the two combine to solve range-finding problems efficiently.

What You Will Learn

By the end of this page, you will understand: (1) Why rightmost search requires different update rules than leftmost, (2) The modified invariant for rightmost binary search, (3) How to implement rightmost search correctly, (4) How to combine leftmost and rightmost search for range queries, (5) The relationship to Python's bisect_right and C++'s upper_bound.

The Rightmost Boundary Concept

Just as leftmost search finds the boundary between "less than" and "greater than or equal," rightmost search finds a different boundary:

Rightmost Search: Find the boundary between elements less than or equal to the target and elements strictly greater than the target.

This boundary position tells us where the target's range ends—one past the last occurrence. Let's visualize this with our familiar example:

Comparing Leftmost and Rightmost Boundaries for target = 3
Index	Value	Leftmost Predicate (≥3)	Rightmost Predicate (>3)
0	1	False	False
1	2	False	False
2	3	True ← FIRST TRUE	False
3	3	True	False
4	3	True	False
5	3	True	False ← LAST FALSE
6	4	True	True ← FIRST TRUE
7	5	True	True

Key Observations:

Search Type	Predicate	Boundary Meaning	For target=3 in [1,2,3,3,3,3,4,5]
Leftmost	`arr[i] >= target`	First index where predicate is True	2 (first 3)
Rightmost	`arr[i] > target`	First index where predicate is True	6 (first element after all 3s)

The Critical Insight:

Rightmost search returns the position one past the last occurrence. To get the actual index of the last occurrence:

last_occurrence = rightmost_boundary - 1

But we must verify that this position actually contains our target (it might not if the target doesn't exist).

Why "One Past" is Useful

Returning the position after the last occurrence has elegant properties: • The range [leftmost, rightmost) is a half-open interval containing all occurrences • rightmost - leftmost gives the count of occurrences • If leftmost == rightmost, the target doesn't exist • Consistent with C++ STL conventions (lower_bound, upper_bound)

Two Approaches to Rightmost Search

There are two equivalent ways to think about rightmost binary search. Understanding both deepens your intuition and helps you adapt to different problem formulations.

Approach 1: Find First Greater Than Target

We search for the first index where arr[i] > target. This is exactly bisect_right / upper_bound. The last occurrence of target is at position boundary - 1.

Approach 2: Modified Leftmost Search

We can reuse the leftmost search logic but change when we move the pointers:

When arr[mid] <= target: move left pointer (we haven't gone far enough right yet)
When arr[mid] > target: move right pointer

Both approaches yield the same result. Let's see them in action:

Approach 1: First Greater Than

•Predicate: arr[i] > target
•Find first index where predicate is True
•Last occurrence at boundary - 1
•Same structure as leftmost search
•Maps directly to bisect_right

Approach 2: Modified Updates

•Predicate: arr[i] <= target (push right)
•When true, move left (need to go further)
•When false, move right boundary
•Different update logic than leftmost
•More explicit about "finding last"

Tracing Through Approach 1 (First Greater Than):

Array: [1, 2, 3, 3, 3, 3, 4, 5], target = 3 Predicate: arr[mid] > 3

Iteration	left	right	mid	arr[mid]	arr[mid] > 3?	Action
Init	0	8	-	-	-	Setup
1	0	8	4	3	False	left = 5
2	5	8	6	4	True	right = 6
3	5	6	5	3	False	left = 6
End	6	6	-	-	-	Boundary = 6

Boundary = 6. Last occurrence = 6 - 1 = 5. ✓ (arr[5] = 3)

The Rightmost Loop Invariant

Just as we used a loop invariant to prove leftmost search correct, we need a precise invariant for rightmost search. The invariant changes slightly to reflect our different boundary goal.

The Rightmost Binary Search Invariant

Invariant: At all times during execution: • All elements at indices < left are definitely ≤ target (the left region) • All elements at indices ≥ right are definitely > target (the right region) • Elements in the range [left, right) are unexplored

When the loop terminates (left == right), the unexplored region is empty, and left points to the boundary—the first position where arr[left] > target.

Comparing the Two Invariants:

                       LEFTMOST INVARIANT
                       Boundary: first arr[i] >= target
[  definitely < target  ][  unexplored  ][  definitely >= target  ]
                         ^              ^
                        left          right

                       RIGHTMOST INVARIANT  
                       Boundary: first arr[i] > target
[  definitely <= target  ][  unexplored  ][  definitely > target  ]
                          ^              ^
                         left          right

The Subtle But Critical Difference:

Leftmost: Left region is < target, Right region is >= target
Rightmost: Left region is <= target, Right region is > target

This flips whether the == target case belongs to the left or right region, which determines what we do when arr[mid] == target:

Leftmost: When equal, arr[mid] >= target is true → update right = mid
Rightmost: When equal, arr[mid] > target is false → update left = mid + 1

Invariant Trace: Finding first > 3 in [1, 2, 3, 3, 3, 3, 4, 5]
Iteration	left	right	mid	arr[mid]	arr[mid] > 3?	Action	Invariant Status
Init	0	8				Setup	Trivially true
1	0	8	4	3	False (3 ≤ 3)	left = 5	[0,5) is ≤ 3 ✓
2	5	8	6	4	True (4 > 3)	right = 6	[6,8) is > 3 ✓
3	5	6	5	3	False (3 ≤ 3)	left = 6	[0,6) is ≤ 3 ✓
End	6	6				Exit	Boundary = 6

The Rightmost Binary Search Algorithm

Now let's implement rightmost binary search with the same rigor we applied to leftmost search.

Algorithm Overview:

Initialize left = 0, right = len(arr) (right is exclusive)
While left < right (unexplored region is non-empty):
- Compute mid = left + (right - left) // 2
- If arr[mid] <= target: left = mid + 1 (need to search further right)
- Else (if arr[mid] > target): right = mid
Return left (the boundary = first position where arr[i] > target)
The last occurrence is at left - 1 (if it exists)

rightmost_binary_search.py
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
def rightmost_binary_search(arr: list, target: int) -> int:
    """
    Find the rightmost (last) occurrence of target in a sorted array.
    
    Returns the index of the last occurrence of target.
    Returns -1 if target is not in the array.
    
    Time Complexity: O(log n) - guaranteed
    Space Complexity: O(1)
    
    Invariant maintained throughout:
    - All elements at indices < left are definitely <= target
    - All elements at indices >= right are definitely > target
    - Elements in [left, right) are unexplored
    """
    if not arr:
        return -1
    
    left = 0
    right = len(arr)  # Exclusive right boundary
    
    # Find the first position where arr[i] > target
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] <= target:
            # arr[mid] is in the left region (<= target)
            # We need to search further right
            left = mid + 1
        else:
            # arr[mid] > target, so it's in the right region
            right = mid
    
    # left now points to the first position where arr[left] > target
    # The last occurrence of target (if any) is at left - 1
    
    # Check bounds and verify target exists at left - 1
    if left > 0 and arr[left - 1] == target:
        return left - 1
    else:
        return -1
 
 
def rightmost_boundary(arr: list, target: int) -> int:
    """
    Returns the boundary position (one past last occurrence).
    This is equivalent to bisect.bisect_right(arr, target).
    
    Unlike rightmost_binary_search, this always returns a valid position
    (0 to len(arr)), regardless of whether target exists.
    """
    left = 0
    right = len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left  # Always valid: 0 to len(arr)
 
 
# Comprehensive tests
def test_rightmost_binary_search():
    test_cases = [
        # (array, target, expected_last_index, description)
        ([1, 2, 3, 3, 3, 3, 4, 5], 3, 5, "Multiple occurrences - last is at 5"),
        ([1, 2, 3, 4, 5], 3, 2, "Single occurrence"),
        ([1, 2, 4, 5], 3, -1, "Target not present"),
        ([3, 3, 3, 3, 3], 3, 4, "All same - last is at end"),
        ([1, 1, 1, 2, 3], 1, 2, "Target at beginning - last of group"),
        ([1, 2, 3, 5, 5, 5], 5, 5, "Target at end"),
        ([], 3, -1, "Empty array"),
        ([3], 3, 0, "Single element - found"),
        ([5], 3, -1, "Single element - target smaller"),
        ([1], 3, -1, "Single element - target larger"),
        ([1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4], 3, 9, "Many duplicates"),
        ([1, 3, 3, 3, 5], 3, 3, "Duplicates in middle"),
    ]
    
    print("Testing rightmost_binary_search:")
    all_passed = True
    for arr, target, expected, description in test_cases:
        result = rightmost_binary_search(arr, target)
        status = "✓" if result == expected else "✗"
        if result != expected:
            all_passed = False
            print(f"  {status} {description}")
            print(f"      Expected: {expected}, Got: {result}")
        else:
            print(f"  {status} {description}")
    
    print(f"\n{'All tests passed!' if all_passed else 'Some tests failed.'}")
 
 
if __name__ == "__main__":
    test_rightmost_binary_search()

The Critical Difference from Leftmost

Compare the two algorithms:

Leftmost: if arr[mid] < target → left = mid + 1 Rightmost: if arr[mid] <= target → left = mid + 1

The only change is adding the equals sign! But this flips which side of the boundary the equal elements fall on, completely changing what boundary we find.

Library Implementations: bisect_right & upper_bound

Most languages provide built-in rightmost binary search functions. Understanding their semantics is crucial for correct usage.

using_bisect_right.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
import bisect
 
def find_last_occurrence_bisect(arr: list, target: int) -> int:
    """
    Find last occurrence using Python's bisect_right.
    
    bisect_right returns the rightmost position where target  
    could be inserted while maintaining sorted order.
    = first position where arr[i] > target
    = one past the last occurrence of target
    """
    pos = bisect.bisect_right(arr, target)
    
    # Last occurrence is at pos - 1
    if pos > 0 and arr[pos - 1] == target:
        return pos - 1
    return -1
 
 
# Key insight: bisect_left vs bisect_right
arr = [1, 2, 3, 3, 3, 3, 4, 5]
 
# bisect_left: first position where element >= target
print(f"bisect_left(arr, 3) = {bisect.bisect_left(arr, 3)}")   # 2 (first 3)
 
# bisect_right: first position where element > target  
print(f"bisect_right(arr, 3) = {bisect.bisect_right(arr, 3)}")  # 6 (after last 3)
 
# The range of all 3s: [bisect_left, bisect_right)
left = bisect.bisect_left(arr, 3)
right = bisect.bisect_right(arr, 3)
print(f"All 3s are at indices: [{left}, {right})")  # [2, 6)
print(f"Number of 3s: {right - left}")               # 4
 
 
# For non-existent elements, they return the same value
print(f"bisect_left(arr, 3.5) = {bisect.bisect_left(arr, 3.5)}")   # 6
print(f"bisect_right(arr, 3.5) = {bisect.bisect_right(arr, 3.5)}")  # 6
# When left == right, the element doesn't exist
 
 
# Useful pattern: counting elements
def count_equal(arr: list, target: int) -> int:
    """Count occurrences of target in sorted array. O(log n)."""
    return bisect.bisect_right(arr, target) - bisect.bisect_left(arr, target)
 
 
def count_less_than_or_equal(arr: list, target: int) -> int:
    """Count elements <= target. O(log n)."""
    return bisect.bisect_right(arr, target)
 
 
def count_strictly_greater(arr: list, target: int) -> int:
    """Count elements > target. O(log n)."""
    return len(arr) - bisect.bisect_right(arr, target)
 
 
# Examples
print(f"\nCount of 3s: {count_equal(arr, 3)}")                    # 4
print(f"Elements <= 3: {count_less_than_or_equal(arr, 3)}")       # 6
print(f"Elements > 3: {count_strictly_greater(arr, 3)}")          # 2

Complete Comparison: bisect_left vs bisect_right
Property	bisect_left (lower_bound)	bisect_right (upper_bound)
Returns	First position where arr[i] ≥ target	First position where arr[i] > target
When target exists	Index of first occurrence	One past last occurrence
When target missing	Insertion point	Insertion point (same as left)
For counting < target	Returns the count	N/A
For counting ≤ target	N/A	Returns the count
Elements equal to target	At indices [left, right)	At indices [left, right)

The Half-Open Interval [left, right)

The range of all occurrences of target is [bisect_left(arr, target), bisect_right(arr, target)). This half-open interval is elegant: • Length = right - left = count of occurrences • If left == right, interval is empty → target doesn't exist • Consistent with Python slicing: arr[left:right] • No off-by-one confusion about inclusion/exclusion

Combining Leftmost and Rightmost for Range Queries

The true power of leftmost and rightmost binary search emerges when combined for range-based queries. This is a fundamental pattern in algorithm design.

range_queries.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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import bisect
from typing import Tuple, List, Optional
 
# =====================================================
# Pattern 1: Find the range [first, last] of a value
# =====================================================
 
def find_range(arr: List[int], target: int) -> Tuple[int, int]:
    """
    Find the range [first, last] of all occurrences of target.
    Returns (-1, -1) if target is not found.
    
    Time: O(log n) - two binary searches
    Space: O(1)
    """
    left = bisect.bisect_left(arr, target)
    
    # Quick check: if target doesn't exist at left position, it doesn't exist
    if left >= len(arr) or arr[left] != target:
        return (-1, -1)
    
    right = bisect.bisect_right(arr, target)
    
    # Return inclusive range [first, last]
    return (left, right - 1)
 
 
# Example usage
arr = [1, 2, 3, 3, 3, 3, 4, 5]
print(f"Range of 3s: {find_range(arr, 3)}")   # (2, 5)
print(f"Range of 1: {find_range(arr, 1)}")    # (0, 0)
print(f"Range of 10: {find_range(arr, 10)}")  # (-1, -1)
 
 
# =====================================================
# Pattern 2: Count elements in range [low, high]
# =====================================================
 
def count_in_range(arr: List[int], low: int, high: int) -> int:
    """
    Count elements where low <= element <= high.
    
    Key insight:
    - Elements < low: bisect_left(arr, low)
    - Elements <= high: bisect_right(arr, high)
    - Elements in [low, high]: difference
    
    Time: O(log n)
    """
    left = bisect.bisect_left(arr, low)     # First position >= low
    right = bisect.bisect_right(arr, high)  # First position > high
    return right - left
 
 
# Example
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(f"Elements in [3, 7]: {count_in_range(arr, 3, 7)}")  # 5
print(f"Elements in [5, 5]: {count_in_range(arr, 5, 5)}")  # 1
print(f"Elements in [11, 20]: {count_in_range(arr, 11, 20)}")  # 0
 
 
# =====================================================
# Pattern 3: Query sorted time-series data
# =====================================================
 
def events_in_timerange(
    events: List[Tuple[int, str]],
    start_time: int,
    end_time: int
) -> List[Tuple[int, str]]:
    """
    Find all events in [start_time, end_time].
    Events are sorted by timestamp (first element).
    
    Time: O(log n + k) where k is number of matching events
    """
    if not events:
        return []
    
    # Extract timestamps for binary search
    timestamps = [e[0] for e in events]
    
    left = bisect.bisect_left(timestamps, start_time)
    right = bisect.bisect_right(timestamps, end_time)
    
    return events[left:right]
 
 
events = [
    (100, "login"),
    (150, "view_page"),
    (200, "click_button"),
    (250, "purchase"),
    (300, "logout"),
]
 
print(events_in_timerange(events, 150, 250))
# [(150, 'view_page'), (200, 'click_button'), (250, 'purchase')]
 
 
# =====================================================
# Pattern 4: Implementation without bisect (interview-style)
# =====================================================
 
def search_range_from_scratch(arr: List[int], target: int) -> List[int]:
    """
    LeetCode 34: Find First and Last Position of Element in Sorted Array
    
    Returns [first, last] or [-1, -1] if not found.
    Implements both searches from scratch.
    """
    def find_left_boundary(arr: List[int], target: int) -> int:
        """Find first index where arr[i] >= 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 find_right_boundary(arr: List[int], target: int) -> int:
        """Find first index where arr[i] > 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
    
    if not arr:
        return [-1, -1]
    
    left = find_left_boundary(arr, target)
    
    # Check if target exists
    if left >= len(arr) or arr[left] != target:
        return [-1, -1]
    
    right = find_right_boundary(arr, target)
    
    return [left, right - 1]
 
 
# Test with LeetCode examples
print(search_range_from_scratch([5, 7, 7, 8, 8, 10], 8))  # [3, 4]
print(search_range_from_scratch([5, 7, 7, 8, 8, 10], 6))  # [-1, -1]
print(search_range_from_scratch([], 0))                   # [-1, -1]

LeetCode 34: First and Last Position

This is one of the most common binary search interview problems. The key insight is that finding a range requires TWO binary searches: one for the left boundary (first occurrence) and one for the right boundary (one past last occurrence). Each search is O(log n), so the total is O(log n). Resist the urge to do linear scanning after finding one endpoint—that would degrade to O(n).

Edge Cases for Rightmost Search

Rightmost binary search has its own set of edge cases that differ subtly from leftmost search. Let's analyze them systematically.

Edge Cases: Rightmost Binary Search
Edge Case	Array	Target	Boundary (first >)	Last Occurrence	Notes
Empty array	[]	3	0	-1	No elements
Single - found	[3]	3	1	0	Only element matches
Single - too small	[1]	3	1	-1	Target greater, no match
Single - too large	[5]	3	0	-1	Target smaller, no match
All match	[3,3,3,3]	3	4	3	Boundary at end (len)
Target at end	[1,2,3]	3	3	2	Last element matches
Target at start	[3,4,5]	3	1	0	First element matches
Duplicates at end	[1,2,5,5,5]	5	5	4	Multiple at end
Target > all	[1,2,3]	10	3	-1	Boundary at len(arr)
Target < all	[5,6,7]	3	0	-1	Boundary at 0

Key Difference from Leftmost:

For rightmost search, the boundary can be len(arr) when all elements are <= target. This is valid—it means the "first element greater than target" doesn't exist, so all elements are candidates.

The final check is also different:

Leftmost: Check arr[left] == target (boundary is at or after first match)
Rightmost: Check arr[left - 1] == target (boundary is after last match, so we check one before)

Watch the Off-by-One!

The most common bug in rightmost search: forgetting to subtract 1 when converting from boundary to last occurrence. The boundary is the first position GREATER than target, so the last occurrence is at boundary - 1. Always check that boundary > 0 before subtracting!

Summary: Mastering Rightmost Binary Search

Rightmost binary search completes the binary search toolkit. Together with leftmost search, you can now solve any boundary-finding problem on sorted data in O(log n) time.

Key Takeaways

•Rightmost finds a different boundary — The first position where arr[i] > target (one past the last match).
•One character difference — Leftmost uses < in the condition; rightmost uses <=. This flips where equals falls.
•Last occurrence = boundary - 1 — Don't forget to convert from boundary to actual index!
•bisect_right = upper_bound — Library functions exist; know their semantics.
•Range [left, right) is half-open — Length = right - left. Empty means target missing.
•Combine for range queries — Two binary searches give you first and last positions in O(log n) total.

Quick Reference: Leftmost vs Rightmost
Property	Leftmost (bisect_left)	Rightmost (bisect_right)
Predicate	arr[mid] >= target	arr[mid] > target
When arr[mid] < target	left = mid + 1	left = mid + 1
When arr[mid] == target	right = mid	left = mid + 1 ← Different!
When arr[mid] > target	right = mid	right = mid
Result meaning	First position ≥ target	First position > target
To get actual index	Boundary is the answer	Boundary - 1
C++ equivalent	lower_bound	upper_bound

What's Next:

In the next page, we'll explore Finding Insertion Position—a variation where the target may not exist, and we need to find where it should go to maintain sorted order. You'll see how leftmost and rightmost searches naturally extend to this problem.

Page Complete

You've mastered rightmost binary search and understand its relationship to leftmost search. You can now implement both from scratch, use library functions correctly, and combine them for range queries. The boundary-finding mental model will serve you well as we explore more variations.

2 / 5

Loading learning content...

Data Structures & AlgorithmsBinary Search Variations & Edge Cases

Binary Search Variations & Edge Cases

LevelIntermediate

Duration90 mins

TopicBinary Search Variations & Edge Cases

2 / 5

Finding Last Occurrence

The Symmetric Challenge

Real-World Motivations:

"What was the last day our inventory fell below the reorder threshold?"
"Find the rightmost index where a target appears."
"How many elements are less than or equal to a threshold?"
"What is the range [first, last] of all occurrences of a value?"

This page will equip you with a complete understanding of rightmost binary search, its relationship to leftmost search, and how the two combine to solve range-finding problems efficiently.

What You Will Learn

The Rightmost Boundary Concept

Just as leftmost search finds the boundary between "less than" and "greater than or equal," rightmost search finds a different boundary:

Rightmost Search: Find the boundary between elements less than or equal to the target and elements strictly greater than the target.

This boundary position tells us where the target's range ends—one past the last occurrence. Let's visualize this with our familiar example:

Comparing Leftmost and Rightmost Boundaries for target = 3
Index	Value	Leftmost Predicate (≥3)	Rightmost Predicate (>3)
0	1	False	False
1	2	False	False
2	3	True ← FIRST TRUE	False
3	3	True	False
4	3	True	False
5	3	True	False ← LAST FALSE
6	4	True	True ← FIRST TRUE
7	5	True	True

Key Observations:

Search Type	Predicate	Boundary Meaning	For target=3 in [1,2,3,3,3,3,4,5]
Leftmost	`arr[i] >= target`	First index where predicate is True	2 (first 3)
Rightmost	`arr[i] > target`	First index where predicate is True	6 (first element after all 3s)

The Critical Insight:

Rightmost search returns the position one past the last occurrence. To get the actual index of the last occurrence:

last_occurrence = rightmost_boundary - 1

But we must verify that this position actually contains our target (it might not if the target doesn't exist).

Why "One Past" is Useful

Two Approaches to Rightmost Search

There are two equivalent ways to think about rightmost binary search. Understanding both deepens your intuition and helps you adapt to different problem formulations.

Approach 1: Find First Greater Than Target

We search for the first index where arr[i] > target. This is exactly bisect_right / upper_bound. The last occurrence of target is at position boundary - 1.

Approach 2: Modified Leftmost Search

We can reuse the leftmost search logic but change when we move the pointers:

When arr[mid] <= target: move left pointer (we haven't gone far enough right yet)
When arr[mid] > target: move right pointer

Both approaches yield the same result. Let's see them in action:

Approach 1: First Greater Than

•Predicate: arr[i] > target
•Find first index where predicate is True
•Last occurrence at boundary - 1
•Same structure as leftmost search
•Maps directly to bisect_right

Approach 2: Modified Updates

•Predicate: arr[i] <= target (push right)
•When true, move left (need to go further)
•When false, move right boundary
•Different update logic than leftmost
•More explicit about "finding last"

Tracing Through Approach 1 (First Greater Than):

Array: [1, 2, 3, 3, 3, 3, 4, 5], target = 3 Predicate: arr[mid] > 3

Iteration	left	right	mid	arr[mid]	arr[mid] > 3?	Action
Init	0	8	-	-	-	Setup
1	0	8	4	3	False	left = 5
2	5	8	6	4	True	right = 6
3	5	6	5	3	False	left = 6
End	6	6	-	-	-	Boundary = 6

Boundary = 6. Last occurrence = 6 - 1 = 5. ✓ (arr[5] = 3)

The Rightmost Loop Invariant

Just as we used a loop invariant to prove leftmost search correct, we need a precise invariant for rightmost search. The invariant changes slightly to reflect our different boundary goal.

The Rightmost Binary Search Invariant

When the loop terminates (left == right), the unexplored region is empty, and left points to the boundary—the first position where arr[left] > target.

Comparing the Two Invariants:

                       LEFTMOST INVARIANT
                       Boundary: first arr[i] >= target
[  definitely < target  ][  unexplored  ][  definitely >= target  ]
                         ^              ^
                        left          right

                       RIGHTMOST INVARIANT  
                       Boundary: first arr[i] > target
[  definitely <= target  ][  unexplored  ][  definitely > target  ]
                          ^              ^
                         left          right

The Subtle But Critical Difference:

Leftmost: Left region is < target, Right region is >= target
Rightmost: Left region is <= target, Right region is > target

This flips whether the == target case belongs to the left or right region, which determines what we do when arr[mid] == target:

Leftmost: When equal, arr[mid] >= target is true → update right = mid
Rightmost: When equal, arr[mid] > target is false → update left = mid + 1

Invariant Trace: Finding first > 3 in [1, 2, 3, 3, 3, 3, 4, 5]
Iteration	left	right	mid	arr[mid]	arr[mid] > 3?	Action	Invariant Status
Init	0	8				Setup	Trivially true
1	0	8	4	3	False (3 ≤ 3)	left = 5	[0,5) is ≤ 3 ✓
2	5	8	6	4	True (4 > 3)	right = 6	[6,8) is > 3 ✓
3	5	6	5	3	False (3 ≤ 3)	left = 6	[0,6) is ≤ 3 ✓
End	6	6				Exit	Boundary = 6

The Rightmost Binary Search Algorithm

Now let's implement rightmost binary search with the same rigor we applied to leftmost search.

Algorithm Overview:

Initialize left = 0, right = len(arr) (right is exclusive)
While left < right (unexplored region is non-empty):
- Compute mid = left + (right - left) // 2
- If arr[mid] <= target: left = mid + 1 (need to search further right)
- Else (if arr[mid] > target): right = mid
Return left (the boundary = first position where arr[i] > target)
The last occurrence is at left - 1 (if it exists)

rightmost_binary_search.py
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
def rightmost_binary_search(arr: list, target: int) -> int:
    """
    Find the rightmost (last) occurrence of target in a sorted array.
    
    Returns the index of the last occurrence of target.
    Returns -1 if target is not in the array.
    
    Time Complexity: O(log n) - guaranteed
    Space Complexity: O(1)
    
    Invariant maintained throughout:
    - All elements at indices < left are definitely <= target
    - All elements at indices >= right are definitely > target
    - Elements in [left, right) are unexplored
    """
    if not arr:
        return -1
    
    left = 0
    right = len(arr)  # Exclusive right boundary
    
    # Find the first position where arr[i] > target
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] <= target:
            # arr[mid] is in the left region (<= target)
            # We need to search further right
            left = mid + 1
        else:
            # arr[mid] > target, so it's in the right region
            right = mid
    
    # left now points to the first position where arr[left] > target
    # The last occurrence of target (if any) is at left - 1
    
    # Check bounds and verify target exists at left - 1
    if left > 0 and arr[left - 1] == target:
        return left - 1
    else:
        return -1
 
 
def rightmost_boundary(arr: list, target: int) -> int:
    """
    Returns the boundary position (one past last occurrence).
    This is equivalent to bisect.bisect_right(arr, target).
    
    Unlike rightmost_binary_search, this always returns a valid position
    (0 to len(arr)), regardless of whether target exists.
    """
    left = 0
    right = len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left  # Always valid: 0 to len(arr)
 
 
# Comprehensive tests
def test_rightmost_binary_search():
    test_cases = [
        # (array, target, expected_last_index, description)
        ([1, 2, 3, 3, 3, 3, 4, 5], 3, 5, "Multiple occurrences - last is at 5"),
        ([1, 2, 3, 4, 5], 3, 2, "Single occurrence"),
        ([1, 2, 4, 5], 3, -1, "Target not present"),
        ([3, 3, 3, 3, 3], 3, 4, "All same - last is at end"),
        ([1, 1, 1, 2, 3], 1, 2, "Target at beginning - last of group"),
        ([1, 2, 3, 5, 5, 5], 5, 5, "Target at end"),
        ([], 3, -1, "Empty array"),
        ([3], 3, 0, "Single element - found"),
        ([5], 3, -1, "Single element - target smaller"),
        ([1], 3, -1, "Single element - target larger"),
        ([1, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4], 3, 9, "Many duplicates"),
        ([1, 3, 3, 3, 5], 3, 3, "Duplicates in middle"),
    ]
    
    print("Testing rightmost_binary_search:")
    all_passed = True
    for arr, target, expected, description in test_cases:
        result = rightmost_binary_search(arr, target)
        status = "✓" if result == expected else "✗"
        if result != expected:
            all_passed = False
            print(f"  {status} {description}")
            print(f"      Expected: {expected}, Got: {result}")
        else:
            print(f"  {status} {description}")
    
    print(f"\n{'All tests passed!' if all_passed else 'Some tests failed.'}")
 
 
if __name__ == "__main__":
    test_rightmost_binary_search()

The Critical Difference from Leftmost

Compare the two algorithms:

Leftmost: if arr[mid] < target → left = mid + 1 Rightmost: if arr[mid] <= target → left = mid + 1

The only change is adding the equals sign! But this flips which side of the boundary the equal elements fall on, completely changing what boundary we find.

Library Implementations: bisect_right & upper_bound

Most languages provide built-in rightmost binary search functions. Understanding their semantics is crucial for correct usage.

using_bisect_right.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
import bisect
 
def find_last_occurrence_bisect(arr: list, target: int) -> int:
    """
    Find last occurrence using Python's bisect_right.
    
    bisect_right returns the rightmost position where target  
    could be inserted while maintaining sorted order.
    = first position where arr[i] > target
    = one past the last occurrence of target
    """
    pos = bisect.bisect_right(arr, target)
    
    # Last occurrence is at pos - 1
    if pos > 0 and arr[pos - 1] == target:
        return pos - 1
    return -1
 
 
# Key insight: bisect_left vs bisect_right
arr = [1, 2, 3, 3, 3, 3, 4, 5]
 
# bisect_left: first position where element >= target
print(f"bisect_left(arr, 3) = {bisect.bisect_left(arr, 3)}")   # 2 (first 3)
 
# bisect_right: first position where element > target  
print(f"bisect_right(arr, 3) = {bisect.bisect_right(arr, 3)}")  # 6 (after last 3)
 
# The range of all 3s: [bisect_left, bisect_right)
left = bisect.bisect_left(arr, 3)
right = bisect.bisect_right(arr, 3)
print(f"All 3s are at indices: [{left}, {right})")  # [2, 6)
print(f"Number of 3s: {right - left}")               # 4
 
 
# For non-existent elements, they return the same value
print(f"bisect_left(arr, 3.5) = {bisect.bisect_left(arr, 3.5)}")   # 6
print(f"bisect_right(arr, 3.5) = {bisect.bisect_right(arr, 3.5)}")  # 6
# When left == right, the element doesn't exist
 
 
# Useful pattern: counting elements
def count_equal(arr: list, target: int) -> int:
    """Count occurrences of target in sorted array. O(log n)."""
    return bisect.bisect_right(arr, target) - bisect.bisect_left(arr, target)
 
 
def count_less_than_or_equal(arr: list, target: int) -> int:
    """Count elements <= target. O(log n)."""
    return bisect.bisect_right(arr, target)
 
 
def count_strictly_greater(arr: list, target: int) -> int:
    """Count elements > target. O(log n)."""
    return len(arr) - bisect.bisect_right(arr, target)
 
 
# Examples
print(f"\nCount of 3s: {count_equal(arr, 3)}")                    # 4
print(f"Elements <= 3: {count_less_than_or_equal(arr, 3)}")       # 6
print(f"Elements > 3: {count_strictly_greater(arr, 3)}")          # 2

Complete Comparison: bisect_left vs bisect_right
Property	bisect_left (lower_bound)	bisect_right (upper_bound)
Returns	First position where arr[i] ≥ target	First position where arr[i] > target
When target exists	Index of first occurrence	One past last occurrence
When target missing	Insertion point	Insertion point (same as left)
For counting < target	Returns the count	N/A
For counting ≤ target	N/A	Returns the count
Elements equal to target	At indices [left, right)	At indices [left, right)

The Half-Open Interval [left, right)

Combining Leftmost and Rightmost for Range Queries

The true power of leftmost and rightmost binary search emerges when combined for range-based queries. This is a fundamental pattern in algorithm design.

range_queries.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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
import bisect
from typing import Tuple, List, Optional
 
# =====================================================
# Pattern 1: Find the range [first, last] of a value
# =====================================================
 
def find_range(arr: List[int], target: int) -> Tuple[int, int]:
    """
    Find the range [first, last] of all occurrences of target.
    Returns (-1, -1) if target is not found.
    
    Time: O(log n) - two binary searches
    Space: O(1)
    """
    left = bisect.bisect_left(arr, target)
    
    # Quick check: if target doesn't exist at left position, it doesn't exist
    if left >= len(arr) or arr[left] != target:
        return (-1, -1)
    
    right = bisect.bisect_right(arr, target)
    
    # Return inclusive range [first, last]
    return (left, right - 1)
 
 
# Example usage
arr = [1, 2, 3, 3, 3, 3, 4, 5]
print(f"Range of 3s: {find_range(arr, 3)}")   # (2, 5)
print(f"Range of 1: {find_range(arr, 1)}")    # (0, 0)
print(f"Range of 10: {find_range(arr, 10)}")  # (-1, -1)
 
 
# =====================================================
# Pattern 2: Count elements in range [low, high]
# =====================================================
 
def count_in_range(arr: List[int], low: int, high: int) -> int:
    """
    Count elements where low <= element <= high.
    
    Key insight:
    - Elements < low: bisect_left(arr, low)
    - Elements <= high: bisect_right(arr, high)
    - Elements in [low, high]: difference
    
    Time: O(log n)
    """
    left = bisect.bisect_left(arr, low)     # First position >= low
    right = bisect.bisect_right(arr, high)  # First position > high
    return right - left
 
 
# Example
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(f"Elements in [3, 7]: {count_in_range(arr, 3, 7)}")  # 5
print(f"Elements in [5, 5]: {count_in_range(arr, 5, 5)}")  # 1
print(f"Elements in [11, 20]: {count_in_range(arr, 11, 20)}")  # 0
 
 
# =====================================================
# Pattern 3: Query sorted time-series data
# =====================================================
 
def events_in_timerange(
    events: List[Tuple[int, str]],
    start_time: int,
    end_time: int
) -> List[Tuple[int, str]]:
    """
    Find all events in [start_time, end_time].
    Events are sorted by timestamp (first element).
    
    Time: O(log n + k) where k is number of matching events
    """
    if not events:
        return []
    
    # Extract timestamps for binary search
    timestamps = [e[0] for e in events]
    
    left = bisect.bisect_left(timestamps, start_time)
    right = bisect.bisect_right(timestamps, end_time)
    
    return events[left:right]
 
 
events = [
    (100, "login"),
    (150, "view_page"),
    (200, "click_button"),
    (250, "purchase"),
    (300, "logout"),
]
 
print(events_in_timerange(events, 150, 250))
# [(150, 'view_page'), (200, 'click_button'), (250, 'purchase')]
 
 
# =====================================================
# Pattern 4: Implementation without bisect (interview-style)
# =====================================================
 
def search_range_from_scratch(arr: List[int], target: int) -> List[int]:
    """
    LeetCode 34: Find First and Last Position of Element in Sorted Array
    
    Returns [first, last] or [-1, -1] if not found.
    Implements both searches from scratch.
    """
    def find_left_boundary(arr: List[int], target: int) -> int:
        """Find first index where arr[i] >= 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 find_right_boundary(arr: List[int], target: int) -> int:
        """Find first index where arr[i] > 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
    
    if not arr:
        return [-1, -1]
    
    left = find_left_boundary(arr, target)
    
    # Check if target exists
    if left >= len(arr) or arr[left] != target:
        return [-1, -1]
    
    right = find_right_boundary(arr, target)
    
    return [left, right - 1]
 
 
# Test with LeetCode examples
print(search_range_from_scratch([5, 7, 7, 8, 8, 10], 8))  # [3, 4]
print(search_range_from_scratch([5, 7, 7, 8, 8, 10], 6))  # [-1, -1]
print(search_range_from_scratch([], 0))                   # [-1, -1]

LeetCode 34: First and Last Position

Edge Cases for Rightmost Search

Rightmost binary search has its own set of edge cases that differ subtly from leftmost search. Let's analyze them systematically.

Edge Cases: Rightmost Binary Search
Edge Case	Array	Target	Boundary (first >)	Last Occurrence	Notes
Empty array	[]	3	0	-1	No elements
Single - found	[3]	3	1	0	Only element matches
Single - too small	[1]	3	1	-1	Target greater, no match
Single - too large	[5]	3	0	-1	Target smaller, no match
All match	[3,3,3,3]	3	4	3	Boundary at end (len)
Target at end	[1,2,3]	3	3	2	Last element matches
Target at start	[3,4,5]	3	1	0	First element matches
Duplicates at end	[1,2,5,5,5]	5	5	4	Multiple at end
Target > all	[1,2,3]	10	3	-1	Boundary at len(arr)
Target < all	[5,6,7]	3	0	-1	Boundary at 0

Key Difference from Leftmost:

For rightmost search, the boundary can be len(arr) when all elements are <= target. This is valid—it means the "first element greater than target" doesn't exist, so all elements are candidates.

The final check is also different:

Leftmost: Check arr[left] == target (boundary is at or after first match)
Rightmost: Check arr[left - 1] == target (boundary is after last match, so we check one before)

Watch the Off-by-One!

Summary: Mastering Rightmost Binary Search

Rightmost binary search completes the binary search toolkit. Together with leftmost search, you can now solve any boundary-finding problem on sorted data in O(log n) time.

Key Takeaways

•Rightmost finds a different boundary — The first position where arr[i] > target (one past the last match).
•One character difference — Leftmost uses < in the condition; rightmost uses <=. This flips where equals falls.
•Last occurrence = boundary - 1 — Don't forget to convert from boundary to actual index!
•bisect_right = upper_bound — Library functions exist; know their semantics.
•Range [left, right) is half-open — Length = right - left. Empty means target missing.
•Combine for range queries — Two binary searches give you first and last positions in O(log n) total.

Quick Reference: Leftmost vs Rightmost
Property	Leftmost (bisect_left)	Rightmost (bisect_right)
Predicate	arr[mid] >= target	arr[mid] > target
When arr[mid] < target	left = mid + 1	left = mid + 1
When arr[mid] == target	right = mid	left = mid + 1 ← Different!
When arr[mid] > target	right = mid	right = mid
Result meaning	First position ≥ target	First position > target
To get actual index	Boundary is the answer	Boundary - 1
C++ equivalent	lower_bound	upper_bound

What's Next:

Page Complete

2 / 5