Find First and Last Position in a Sorted Array

Plain binary search returns an index that holds the target. With repeated values that is not enough. "When did this user first log in?", "how many orders cost exactly 499?", "which rows fall in this date range?" all need the edges of a run of equal values, not a random point inside it.

This problem is how interviewers test whether you know the boundary search. Most candidates find the target and then walk outwards, which is quietly linear. The strong answer is two binary searches that differ in one character.

The problem

You are given a list of integers sorted in non-decreasing order, so values may repeat, and a target. Return a pair [first, last]: the index of the first and the last copy of the target. If the target does not appear, return [-1, -1].

• nums = [1, 2, 2, 2, 3, 5], target = 2 → [1, 3]. The 2s sit at indices 1, 2 and 3.
• Same nums, target = 4 → [-1, -1]. There is no 4.

Constraints: 0 ≤ len(nums) ≤ 10⁵, values up to 10⁹ in size, and the solution must run in O(log n).

Clarifying questions

• Can the list be empty? Yes. Return [-1, -1].
• Is it sorted ascending? Yes, non-decreasing: equal neighbours are allowed.
• Indices or values? Indices, as a two-element list.
• Could the whole list be the target? Yes. That is the case that breaks the "find then walk outwards" idea.

Approach 1: the simple way

Scan once. Remember the first index where you see the target, and keep updating the last.

1def search_range_linear(nums: list[int], target: int) -> list[int]:2    """First and last index of target by scanning: O(n)."""3    first = last = -14    for i, value in enumerate(nums):5        if value == target:6            if first == -1:7                first = i8            last = i9    return [first, last]

Time: O(n). Space: O(1).

A cleverer-looking version finds any copy with binary search and then walks left and right to the ends of the run. That is O(log n + k) where k is the number of copies. On an array of 10⁵ copies of the same value, k = n, so it is linear again. The problem asks for O(log n) in the worst case, so both are out.

The key insight

Stop searching for the target. Search for the two boundaries around it.

For [1, 2, 2, 2, 3, 5] and t = 2, lower bound is 1 (the first 2) and upper bound is 4 (the 3). So the first copy is at 1 and the last at 4 - 1 = 3.

Each bound is a first-true search. For the lower bound, the test "is nums[i] >= t?" reads no, no, yes, yes. For the upper bound, "is nums[i] > t?" does the same. Neither search stops when it sees a copy of the target: seeing a 2 at mid only tells the lower-bound search that the first 2 is at mid or further left, so it keeps mid and keeps going. That is why a run of 10⁵ copies costs 17 steps, not 10⁵.

Approach 2: two boundary searches

1def lower_bound_idx(nums: list[int], target: int) -> int:2    """First index with nums[i] >= target (len(nums) if none)."""3    left, right = 0, len(nums)4    while left < right:5        mid = left + (right - left) // 26        if nums[mid] < target:7            left = mid + 18        else:9            right = mid10    return left111213def upper_bound_idx(nums: list[int], target: int) -> int:14    """First index with nums[i] > target (len(nums) if none)."""15    left, right = 0, len(nums)16    while left < right:17        mid = left + (right - left) // 218        if nums[mid] <= target:              # the only change: equal values count as "too small"19            left = mid + 120        else:21            right = mid22    return left232425def search_range(nums: list[int], target: int) -> list[int]:26    """First and last index of target in sorted nums, or [-1, -1]."""27    first = lower_bound_idx(nums, target)28    if first == len(nums) or nums[first] != target:29        return [-1, -1]                      # lower bound is only a position; check it holds target30    last = upper_bound_idx(nums, target) - 131    return [first, last]

The two searches differ in one character: < versus <=. In the lower bound, a value equal to the target counts as "possibly the answer", so the search keeps it and moves left. In the upper bound, an equal value counts as "too small", so the search moves past it to the right.

Dry run of the lower bound on [1, 2, 2, 2, 3, 5], target 2:

Step 1 lands on a 2 and does not stop. It keeps index 3 as a candidate and looks left, which finds the first 2 at index 1.

The upper bound on the same input:

So search_range returns [1, 4 - 1] = [1, 3].

For target 4, the lower bound runs mid = 3 (2, go right), mid = 5 (5, keep), mid = 4 (3, go right) and returns 5. nums[5] is 5, not 4, so the check returns [-1, -1] without running the second search.

Time: O(log n) — two searches of about 17 steps each at n = 10⁵, whatever the number of copies. Space: O(1).

The two bounds answer a whole family of questions, which is why they are worth learning as a pair:

Python's bisect_left and bisect_right are these two functions. C++ has std::lower_bound and std::upper_bound. Java's Arrays.binarySearch is not a boundary search: with duplicates it returns any matching index.

Edge cases

• Target bigger than everything: the lower bound is len(nums). The check first == len(nums) must come before nums[first], or you read past the end.
• Target smaller than everything: the lower bound is 0 and nums[0] is not the target, so the answer is [-1, -1].
• Empty list: the lower bound is 0, which equals len(nums), so the first check catches it.
• Every value is the target: [7, 7, 7] gives lower bound 0 and upper bound 3, so [0, 2], still in about 2 × log₂ n steps.
• One element: [7] with 7 gives [0, 0].

Follow-ups

• "Count the copies." upper_bound - lower_bound, with no need to check presence: it is 0 when the target is absent.
• "Only integers — can you use one function?" Yes: upper_bound(t) equals lower_bound(t + 1) for integers. It breaks for floats or strings, so say so.
• "Find the k values closest to x." Lower bound gives the position of x; then grow a window left and right with two pointers, or binary search the window's left edge directly.