Find First and Last Position of Element in Sorted Array (LeetCode 34)

The problem

You get an array nums sorted in non-decreasing order (duplicates allowed) and a target. Return [first, last], the first and last indices where target appears. If it doesn’t appear, return [-1, -1]. It must run in O(log n).

Input:  nums = [5, 7, 7, 8, 8, 10], target = 8
Output: [3, 4]

The two 8s sit at indices 3 and 4.

How to think about it

Start with brute force. Scan for the first 8 and keep going until the last one: O(n). A smarter-looking variant is to binary-search for any 8 and then walk left and right. That is still O(n) in the worst case, for example when the whole array is 8s.

Turn “first” and “last” into boundaries. The first index of target is the first position where nums[i] >= target. That is the lower bound. The position just after the last target is the first position where nums[i] > target. That is the upper bound. Both are “first true” questions on sorted data, so each is a single O(log n) boundary search.

The key insight: two boundary searches, not one exact search. Run bisect_left(nums, target) to get lo. If lo is off the end, or nums[lo] isn’t the target, the target isn’t present: return [-1, -1]. Otherwise the last index is bisect_right(nums, target) - 1. The two searches never walk, so duplicates cost nothing extra.

Which pattern is this? Binary search for boundaries. The tell is duplicates in a sorted array and a question about the first or last occurrence, or about how many times something appears (bisect_right - bisect_left).

Approach

1. lo = bisect_left(nums, target): the first index with nums[i] >= target.
2. If lo == len(nums) or nums[lo] != target, return [-1, -1].
3. Otherwise return [lo, bisect_right(nums, target) - 1], since bisect_right gives the first index with nums[i] > target.

Solution

import bisect

def search_range(nums, target):
    lo = bisect.bisect_left(nums, target)                     # first index >= target
    if lo == len(nums) or nums[lo] != target: return [-1, -1] # target absent
    return [lo, bisect.bisect_right(nums, target) - 1]        # first index > target, minus 1
# search_range([5,7,7,8,8,10], 8) -> [3,4]
# search_range([5,7,7,8,8,10], 6) -> [-1,-1]

If you’re asked to avoid the library, write one helper lower_bound(x) (the half-open lo < hi loop) and use lower_bound(target) and lower_bound(target + 1) - 1 for integers.

Dry run

On nums = [5, 7, 7, 8, 8, 10]:

For 8, the upper bound is index 5 (the 10), so the last 8 is at index 4. For 6, the lower bound lands on a 7, so 6 is absent.

Complexity

• Time: O(log n). Two binary searches, each O(log n).
• Space: O(1).

Edge cases and pitfalls

• Empty array: bisect_left returns 0, which equals len(nums), so you return [-1, -1]. Check the bound before reading nums[lo].
• Target bigger than everything: lo == len(nums); the same guard avoids an index error.
• Single occurrence: both ends are the same index, e.g. [5, 8, 9] with target 8 gives [1, 1].
• Find-then-expand looks O(log n) but degrades to O(n) when the target repeats many times.
• Off-by-one on the right end: bisect_right points one past the last copy, so subtract 1.

Related problems

• Search Insert Position (LeetCode 35): the lower bound on its own.
• Time Based Key-Value Store (LeetCode 981): bisect_right - 1 to find the latest entry at or before a timestamp.
• Binary Search (LeetCode 704): the exact-match search, for when values are distinct.