Find First and Last Position of a Value: Lower and Upper Bound Binary Search

Problem

You get a list of integers sorted in ascending order, where values may repeat, and a target. Return a pair [first, last]: the index of the first occurrence and of the last occurrence of the target. If the target does not appear, return [-1, -1]. The solution must run in O(log n).

This is widely known as LeetCode 34 (Find First and Last Position of Element in Sorted Array). It is the cleanest way to show you understand lower bound and upper bound searches, which most other binary search problems reuse.

Constraints for this version: 0 to 100,000 values, each a 32-bit signed integer.

Examples

nums	target	Result
[3, 4, 4, 4, 9, 12, 12]	4	[1, 3]
[3, 4, 4, 4, 9, 12, 12]	12	[5, 6]
[3, 4, 4, 4, 9, 12, 12]	10	[-1, -1]
[6, 6, 6]	6	[0, 2]
[]	1	[-1, -1]

Approach 1: brute force

Scan once, remembering the first and last index where the value matches.

def search_range_linear(nums, target):
    first = last = -1
    for i, v in enumerate(nums):
        if v == target:
            if first == -1:
                first = i
            last = i
    return [first, last]

O(n) time. A common half-way answer is “binary search to any match, then walk left and right”. That is still O(n) in the worst case, for example when every value equals the target, so call it out rather than presenting it as optimal.

Approach 2: optimal

Key insight. Instead of searching for the target itself, search for a boundary:

• lower_bound(t): the first index i with nums[i] >= t (or len(nums) if none).
• upper_bound(t): the first index i with nums[i] > t.

All copies of the target sit in [lower_bound, upper_bound). Both are “first index where a condition becomes true” searches, so they share one template with a half-open range [lo, hi).

Walkthrough for nums = [3, 4, 4, 4, 9, 12, 12], t = 4, lower bound (condition: value at least 4):

lo	hi	mid	nums[mid]	Condition	Update
0	7	3	4	true	hi = 3
0	3	1	4	true	hi = 1
0	1	0	3	false	lo = 1

lo == hi == 1, so the first 4 is at index 1. The upper bound search with “value greater than 4” ends at index 4, so the last 4 is at index 3.

def lower_bound(nums, t):
    lo, hi = 0, len(nums)            # answer is in [lo, hi]; hi = len means "none"
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] >= t:
            hi = mid
        else:
            lo = mid + 1
    return lo

def upper_bound(nums, t):
    lo, hi = 0, len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] > t:
            hi = mid
        else:
            lo = mid + 1
    return lo

def search_range(nums, target):
    first = lower_bound(nums, target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    return [first, upper_bound(nums, target) - 1]

Python’s standard library already has both searches: bisect_left is the lower bound and bisect_right the upper bound.

from bisect import bisect_left, bisect_right

def search_range_bisect(nums, target):
    lo = bisect_left(nums, target)
    if lo == len(nums) or nums[lo] != target:
        return [-1, -1]
    return [lo, bisect_right(nums, target) - 1]

Complexity. Two O(log n) searches: O(log n) time, O(1) space. As a bonus, upper_bound - lower_bound counts occurrences in O(log n).

Tests

def check(fn):
    data = [3, 4, 4, 4, 9, 12, 12]
    assert fn(data, 4) == [1, 3]
    assert fn(data, 12) == [5, 6]
    assert fn(data, 3) == [0, 0]
    assert fn(data, 9) == [4, 4]
    for missing in [0, 5, 10, 13]:
        assert fn(data, missing) == [-1, -1]
    assert fn([], 1) == [-1, -1]
    assert fn([6], 6) == [0, 0] and fn([6], 5) == [-1, -1]
    assert fn([6, 6, 6], 6) == [0, 2]                # all duplicates
    big = [1] * 50_000 + [2] * 50_000
    assert fn(big, 1) == [0, 49_999] and fn(big, 2) == [50_000, 99_999]

for fn in (search_range_linear, search_range, search_range_bisect):
    check(fn)

data = [3, 4, 4, 4, 9, 12, 12]
assert upper_bound(data, 4) - lower_bound(data, 4) == 3     # count of 4s
assert lower_bound(data, 100) == len(data) and upper_bound(data, -1) == 0
print("all first/last position tests passed")

Edge cases and pitfalls

• Check the lower bound before using it. It can equal len(nums) (target larger than everything) or point at a bigger value (target missing). Indexing without the check raises IndexError or returns a wrong pair.
• hi = len(nums), not len(nums) - 1. The half-open template needs room for “past the end” as an answer.
• >= versus >. That single character is the only difference between lower and upper bound. Mixing them up shifts the answer by the run length.
• Walking outwards from a match looks logarithmic but is O(n) on long runs of duplicates.

Where this shows up in data engineering

Lower and upper bounds are how you slice a sorted list by key or time range: all events between two timestamps, all rows for one customer in a file sorted by customer id, or the files whose sorted min/max ranges overlap a query. The bisect module makes this a two-line operation in Python scripts and UDFs.