Find First and Last Position of Element in Sorted Array

A standard binary search finds a match. This problem asks for the entire matching block. The difference is one boundary decision.

Read the Search Contract

You receive a non-decreasing integer array nums and a target. Return:

[first index containing target, last index containing target]

If the target does not occur, return:

[-1, -1]

For example:

nums = [5, 7, 7, 8, 8, 10]
target = 8
answer = [3, 4]

The array is sorted, so equal values are contiguous. That gives us structure to exploit. The required runtime is O(log n), so scanning every element is not acceptable as the final approach.

The key observation is that the answer is an interval with two separate boundaries:

• Where does the block of target values begin?
• Where does that block stop?

We will answer those questions with two binary searches.

Recognize the Boundary-Search Pattern

Ordinary binary search usually has this shape:

1. Inspect nums[mid].
2. Return immediately if it equals target.
3. Otherwise discard half of the search interval.

That works when any matching index is sufficient. Here, it is incomplete. If the array contains several copies of the target, the midpoint may land in the middle of the block.

For example:

nums = [5, 7, 7, 8, 8, 10]
                  ^
                mid

Finding index 3 happens to find the first 8 in this example, but a different midpoint or array size could land on index 4. Returning immediately would produce a valid match but an invalid range.

The brute-force baseline is straightforward:

first = -1
last = -1

for i, value in enumerate(nums):
    if value == target:
        if first == -1:
            first = i
        last = i

This uses O(n) time and O(1) extra space. It is useful as a correctness baseline, but it ignores the sorted order.

The stronger model is to search for a monotonic transition rather than for equality.

A predicate is monotonic here if it starts false and then becomes true without switching back:

nums[i] >= target
False False False True True True

or:

nums[i] > target
False False False False True True

Binary search is well suited to finding the first True.

Split the Range Into Two Bounds

Define two insertion positions.

Lower bound

The lower bound is the first index i such that:

nums[i] >= target

For the example:

nums = [5, 7, 7, 8, 8, 10]
target = 8

nums[i] >= 8
False False False True True True
                     ^
                   index 3

So:

lower_bound = 3

If the target exists, this is its first occurrence.

Upper bound

The upper bound is the first index j such that:

nums[j] > target

For the same input:

nums[i] > 8
False False False False False True
                               ^
                             index 5

So:

upper_bound = 5

This is one position after the last occurrence. The target occupies the half-open interval:

[lower_bound, upper_bound)

Therefore, the inclusive answer is:

[lower_bound, upper_bound - 1]

This formulation handles duplicates cleanly. It also handles a target appearing at the beginning or end of the array because the bounds are insertion positions, not special-case match indices.

The lower-bound result also gives us the absence check:

lower == len(nums) or nums[lower] != target

If either condition is true, there is no target in the array.

Preserve the Shrinking Interval

Use a half-open candidate interval:

[lo, hi)

Initialize it as:

lo = 0
hi = len(nums)

The value hi = len(nums) is intentional. It represents a valid insertion position just after the final array element. This lets the search return n when no element satisfies the predicate.

At every iteration, the answer remains somewhere in [lo, hi). The interval shrinks until lo == hi.

For the lower bound, the predicate is:

nums[mid] >= target

If it is true, mid may be the first qualifying index, so we keep mid:

hi = mid

If it is false, mid and everything before it are too small:

lo = mid + 1

For the upper bound, only the predicate changes:

nums[mid] > target

The updates stay the same.

Invariant: At the start of every iteration, the first index satisfying the active predicate is inside [lo, hi). When the interval becomes empty, lo == hi is that first index.

This is the part worth understanding. The algorithm does not depend on the midpoint landing on the correct edge. It preserves every possible edge until only one position remains.

Dry run

For:

nums = [5, 7, 7, 8, 8, 10]
target = 8

The lower-bound search looks for the first value greater than or equal to 8:

lo	hi	mid	nums[mid]	Decision
0	6	3	8	Keep mid: hi = 3
0	3	1	7	Too small: lo = 2
2	3	2	7	Too small: lo = 3

Now lo == hi == 3, so:

lower_bound = 3

The upper-bound search looks for the first value strictly greater than 8:

lo	hi	mid	nums[mid]	Decision
0	6	3	8	Not greater: lo = 4
4	6	5	10	Keep mid: hi = 5
4	5	4	8	Not greater: lo = 5

Now:

upper_bound = 5

The target range is:

[3, 5 - 1] = [3, 4]

Prove the Range Is Correct

The lower-bound search maintains the first index where nums[i] >= target.

When it finishes:

• Every index before lower contains a value less than target.
• lower is the first index whose value is at least target.

If lower == len(nums), every value is smaller than the target. If nums[lower] != target, the first value that could equal the target is already greater than it. Since the array is sorted, the target cannot appear later.

Therefore, this check is sufficient:

if lower == len(nums) or nums[lower] != target:
    return [-1, -1]

For the upper bound:

• Every index before upper contains a value less than or equal to target.
• upper is the first index whose value is greater than target.

So every target occurrence lies between lower and upper - 1, and every index in that interval contains the target. The result is exactly:

[lower, upper - 1]

The proof comes from the invariant. We never discard an index that could still be the boundary.

Implement the Python Solution

A reusable helper can find the first index where either of these predicates becomes true:

nums[i] >= target
nums[i] > target

The strict parameter selects which boundary we want.

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        def first_true(strict: bool) -> int:
            lo = 0
            hi = len(nums)

            while lo < hi:
                mid = (lo + hi) // 2

                if strict:
                    qualifies = nums[mid] > target
                else:
                    qualifies = nums[mid] >= target

                if qualifies:
                    # mid may be the first qualifying index.
                    hi = mid
                else:
                    # mid and everything before it cannot qualify.
                    lo = mid + 1

            return lo

        lower = first_true(strict=False)

        if lower == len(nums) or nums[lower] != target:
            return [-1, -1]

        upper = first_true(strict=True)
        return [lower, upper - 1]

The important implementation choices are deliberate:

• hi starts at len(nums), so the helper can return an insertion position at the end.
• The loop uses [lo, hi), so the search condition is lo < hi.
• When mid qualifies, we assign hi = mid, not mid - 1, because mid is still a possible answer.
• When mid does not qualify, we assign lo = mid + 1, because mid is proven unusable.
• nums[mid] is accessed only while lo < hi. Since mid < hi <= len(nums), mid is always a valid array index.
• The code checks whether lower equals len(nums) before indexing nums[lower].

That last point matters for empty arrays and targets larger than every element. Insertion positions make those cases ordinary instead of forcing sentinel logic into the loop.

Common failure modes

Returning when nums[mid] == target

That finds an arbitrary occurrence. It does not prove that the occurrence is the first or last.

Searching left and right with a linear scan

You can find one match with binary search and then expand outward, but a duplicate-heavy array can make that expansion O(n). The worst case violates the logarithmic requirement.

Mixing interval conventions

A half-open interval [lo, hi) has different updates from a closed interval [lo, hi]. Choose one convention and keep initialization, loop condition, midpoint handling, and updates consistent.

Returning upper as the last index

upper is the first index strictly greater than the target. The last target is immediately before it:

upper - 1

Dry-Run Edge Cases and Failure Modes

These cases expose most boundary bugs:

Input	Expected result	What it checks
nums = [5, 7, 7, 8, 8, 10], target = 6	[-1, -1]	Absent target between values
nums = [], target = 0	[-1, -1]	Empty search interval
nums = [4], target = 4	[0, 0]	Singleton match
nums = [4], target = 3	[-1, -1]	Singleton miss
nums = [2, 2, 2], target = 2	[0, 2]	Entire array is the duplicate block
nums = [1, 2, 3], target = 1	[0, 0]	Target begins at index zero
nums = [1, 2, 3], target = 3	[2, 2]	Target ends at the final index
nums = [5, 7, 7, 8, 8, 10], target = 11	[-1, -1]	Target larger than every value

For the absent target 6, the lower bound lands at index 1, where nums[1] == 7. That is the first value at least 6, but it is not equal to 6, so the target is absent.

For an empty array, both searches return 0. The absence check returns before indexing, producing [-1, -1].

Complexity and the Reusable Rule

Each boundary search halves the candidate interval. Two searches therefore take:

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

The returned pair is part of the output; the helper itself uses only a fixed number of variables.

The reusable pattern is broader than this one problem:

When data is sorted or a condition is monotonic, and the question asks for a first or last position, search for the transition instead of stopping at an arbitrary match.

In an interview, make the implementation reliable by writing these four things before coding:

1. The exact predicate: nums[i] >= target or nums[i] > target.
2. The interval convention: [lo, hi).
3. The invariant: the first qualifying index remains inside the interval.
4. The endpoint tests: empty, singleton, absent, first position, last position, and all values equal.

A duplicate range is just two transitions viewed together. Find the first true position. Find the next first true position. Subtract one from the second boundary. The code becomes short because the reasoning did the heavy lifting.