Problem statement

Given a non-decreasing array nums, find the first and last index of a given target value, returned as [start, end]. If the target is absent, return [-1,-1].

Must run in O(log n) time.

Example 1

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

Example 2

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3

Input: nums = [], target = 0
Output: [-1,-1]

Constraints

• 0 <= nums.length <= 30
• -100 <= nums[i], target <= 100
• nums is sorted non-decreasing.

Hints for Find First and Last Position of Element in Sorted Array

1. Hint 1

   Run two binary searches: lower_bound(target) and lower_bound(target+1) - 1.

2. Hint 2

   If lower_bound lands outside or on a different value, the target is absent.

How to solve Find First and Last Position of Element in Sorted Array

Express both endpoints with the same primitive. lowerBound(v) — the first index whose value is at least v — gives the first occurrence of the target directly, and lowerBound(target + 1) - 1 gives the last, because the first index past the target's block is one step beyond its final element.

Approach

1. Write lowerBound(v): a half-open binary search returning the first index with nums[index] >= v.
2. Compute first = lowerBound(target).
3. If first is past the end or nums[first] is not the target, the value is absent — return [-1, -1].
4. Compute last = lowerBound(target + 1) - 1.
5. Return [first, last].

Why it works

In a non-decreasing array all copies of a value form one contiguous block. lowerBound(target) lands on that block's first index, and lowerBound(target + 1) lands just past its last, so subtracting one gives the final occurrence. Each call is a plain logarithmic search, keeping the whole solution O(log n) — a linear scan outwards from a hit would degrade to O(n) when the array is all one value.

Complexity

• Time — O(log n)
• Space — O(1)

Pitfalls

• Check the presence of the target after the first search — lowerBound returns an insertion point, not a match, and may sit past the end of the array.
• An empty array must return [-1, -1]; the bounds check covers it if written before indexing.
• Do not scan outwards from a found index to widen the range — that is what makes the naive version linear.
• lowerBound(target + 1) - 1 is only valid once the target is known to be present.

Reference solution

Python

from typing import List
import bisect

def searchRange(nums: List[int], target: int) -> List[int]:
    lo = bisect.bisect_left(nums, target)
    if lo == len(nums) or nums[lo] != target:
        return [-1, -1]
    hi = bisect.bisect_right(nums, target) - 1
    return [lo, hi]

Java

public static int[] searchRange(int[] nums, int target) {
    int first = lowerBoundSR(nums, target);
    if (first >= nums.length || nums[first] != target) return new int[]{-1, -1};
    return new int[]{first, lowerBoundSR(nums, target + 1) - 1};
}

private static int lowerBoundSR(int[] nums, int v) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < v) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

C++

int lowerBoundSR(vector<int>& nums, int v) {
    int lo = 0, hi = (int) nums.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < v) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

vector<int> searchRange(vector<int>& nums, int target) {
    int first = lowerBoundSR(nums, target);
    if (first >= (int) nums.size() || nums[first] != target) return vector<int>{-1, -1};
    return vector<int>{first, lowerBoundSR(nums, target + 1) - 1};
}

JavaScript

var searchRange = function(nums, target) {
    function lowerBound(t) {
        let lo = 0, hi = nums.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (nums[mid] < t) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
    const lo = lowerBound(target);
    if (lo === nums.length || nums[lo] !== target) return [-1, -1];
    return [lo, lowerBound(target + 1) - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium