Skip to main content
DSA patterns

Find First and Last Position of Element in Sorted Array

mediumBinary search Must-doMetaAmazonMicrosoft

Problem statement

You're given a list of integers sorted in non-decreasing order (so equal values can sit next to each other), and a target value. Find the index of the first and the last place target appears, and return them as [first, last].

If target isn't in the list at all, return [-1, -1].

Your algorithm has to run in O(log n) time — a plain scan through the list is too slow once it's large.

Examples

Example 1

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

Output: [3, 4]

Explanation: 8 first appears at index 3 and last appears at index 4.

Example 2

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

Output: [-1, -1]

Explanation: 6 never appears in the list, so both positions are -1.

Example 3

Input: nums = [], target = 0

Output: [-1, -1]

Explanation: An empty list has nothing to find, so the answer is the same "not found" pair.

Hints

Hint 1: This is Search Insert Position with a twist — instead of one boundary, you need two: where target starts and where it stops.

Approach

Optimal: Two lower-bound searches

Intuition

This is the same idea as Search Insert Position: a "lower bound" search that finds the first index where nums[index] >= value. Run it once for target — that gives the first index target could sit at. Run it again for target + 1 — that gives the first index after every target, so subtracting 1 gives the last index of target. There's no special-case branch for "found a match" inside the search itself, which is what makes this simpler than Better: one small helper, called twice with different values, does the whole job. Checking nums[start] == target afterwards handles the "not found" case.

Steps

  1. Write a lowerBound(value) helper: left = 0, right = len(nums) (one past the end).
  2. While left < right: compute mid. If nums[mid] >= value, move right = mid. Otherwise move left = mid + 1.
  3. Return left once the loop ends.
  4. Compute start = lowerBound(target).
  5. If start is past the end of the list, or nums[start] != target, target isn't present — return [-1, -1].
  6. Otherwise compute end = lowerBound(target + 1) - 1 and return [start, end].

Dry run

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

lowerBound(8): left=0, right=6 → mid=3, nums[3]=8 ≥ 8 → right=3 → mid=1, nums[1]=7 < 8 → left=2 → mid=2, nums[2]=7 < 8 → left=3 → left==right==3 → returns 3.

lowerBound(9): left=0, right=6 → mid=3, nums[3]=8 < 9 → left=4 → mid=5, nums[5]=10 ≥ 9 → right=5 → mid=4, nums[4]=8 < 9 → left=5 → left==right==5 → returns 5.

start = 3, nums[3] == 8, so it's a match. end = 5 - 1 = 4. Final answer: [3, 4].

Edge cases: when target isn't in the list, lowerBound(target) lands on the index of the next bigger value (or len(nums)), and nums[start] != target catches it, returning [-1, -1]. An empty list makes lowerBound return 0 immediately, and start == n catches that too.

Complexity

Time O(log n) - Still two binary searches back to back, but each one is the plain "lower bound" shape (no branch for an exact match), which is simpler to get right.

Space O(1) - Same handful of index variables as Better.

class Solution:
    def searchRange(self, nums: list[int], target: int) -> list[int]:
        n = len(nums)

        def lowerBound(value: int) -> int:
            left, right = 0, n
            while left < right:
                mid = left + (right - left) // 2
                if nums[mid] >= value:
                    right = mid
                else:
                    left = mid + 1
            return left

        start = lowerBound(target)
        if start == n or nums[start] != target:
            return [-1, -1]
        end = lowerBound(target + 1) - 1
        return [start, end]


if __name__ == "__main__":
    print(Solution().searchRange([5, 7, 7, 8, 8, 10], 8))  # [3, 4]
    print(Solution().searchRange([5, 7, 7, 8, 8, 10], 6))  # [-1, -1]
RecapThe whole problem in a few lines, for the night before
  • Spot it: "sorted array (with duplicates), find the first and last index of a value" — two-boundary binary search
  • Idea: run the lower-bound search twice, once for target and once for target + 1; the gap between the results is the answer
  • Cost: O(log n) time, O(1) space
  • Trap: a normal binary search stops at the first match it finds — that match isn't necessarily the first or last occurrence

Interview follow-ups

  • Instead of the first and last index, return how many times target appears.

    Reuse the same two lower-bound searches. The count is simply end - start + 1 (or 0 if target isn't found) — no extra pass over the list is needed, so it stays O(log n).

  • The list can change between queries — values get inserted while keeping it sorted. How would you support that?

    A plain array makes every insert O(n) because later elements have to shift. Swap it for a balanced structure built for ordered data with fast inserts and range lookups, such as a sorted skip list, a B-tree-backed index (what most databases use), or an order-statistics tree — all keep both "insert a value" and "find the range of a value" at O(log n).

Frequently asked questions

Search Insert Position asks for one boundary — where a value would sit if inserted. This problem asks for two boundaries — the start and the end of a run of equal values — so it runs that same lower-bound search twice, once for target and once for target + 1, and reports the gap between them.

It can, but stopping only tells you that target exists somewhere and gives you one arbitrary matching index — you'd still have no idea whether there are more copies before or after it. That's exactly why Better keeps the search going past the first match instead of returning right away.

The same shape shows up whenever you keep a sorted, timestamp- or version-ordered structure and need the full range of entries matching one value — for example every log line at a given timestamp, or every deployed instance on a specific AMI version, out of a sorted list of many.

None of the three approaches slow down because of it — the binary search approaches only ever look at O(log n) positions regardless of how many matches exist, since they're locating boundaries, not counting every match. Only the brute-force scan's cost depends on where the matches happen to sit, and even then it's bounded by the list's length, not the count of duplicates.