Find First and Last Position
Task example: Find First and Last Position of Element in Sorted Array
Find the first and last indices of target in a non-decreasing integer array nums. Values may repeat. Return [-1, -1] when target is absent, including an empty array. Keep nums unchanged. The required runtime is O(log n); the linear scan below is a baseline.
Indices start at zero. The two 8s occupy indices 3 and 4. A single match has the same first and last index; a missing target keeps both positions at -1.
Linear scan: video explanation
nums = [5, 7, 7, 8, 8, 10], target = 8 → [3, 4]
Prefer reading? Follow the steps below.
- Initialize first = last = -1 and scan all indices. When nums[i] == target, record first only if it is still -1.
- Update last on every match. In the example, index 3 sets both positions to 3; index 4 leaves first unchanged and updates last to 4.
- Return [first, last] after the loop. Returning at the first match would miss later duplicates. If no match occurs, both values remain -1.
Time complexity · O(n)
This implementation visits every element once, so its time complexity is O(n). The empty case takes O(1).
Space complexity · O(1)
Only first, last, and the loop index are stored. The returned pair has fixed size, so extra space is O(1).
Two binary searches: video explanation
nums = [5, 7, 7, 8, 8, 10], target = 8 → [3, 4]
Prefer reading? Follow the steps below.
- Use boundary(first) twice. Each call starts with left = 0, right = len(nums) - 1, and answer = -1.
- If the middle value is smaller, move left to mid + 1; if larger, move right to mid - 1. On equality, save mid and continue instead of returning.
- With first=True, move right leftward after a match. The example saves index 4, then improves it to 3. With first=False, move left rightward after a match; the last index remains 4.
- When each range becomes empty, return its saved answer. Combine the two answers as [first, last]. Missing targets and empty arrays return [-1, -1].
A normal binary search may stop at any duplicate. These searches continue toward opposite boundaries. They avoid the O(n) scan, even when every value equals target.
Time complexity · O(log n)
Each search halves its range, so two searches take O(log n) total time for non-empty input. The constant factor 2 does not change the complexity.
Space complexity · O(1)
The helper is iterative and runs twice in sequence. It stores only a few indices, has constant call depth, and creates no subarrays: O(1) extra space.