Given an array nums sorted in non-decreasing order and a target, return the starting and ending index of target as a two-element array [first, last].
If target is not in the array, return [-1, -1]. Your algorithm must run in O(log n) time.
Example
8 spans indices 3 through 4.
Constraints
- 0 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is sorted in non-decreasing order.
- -10^9 <= target <= 10^9
Intuition
The direct approach scans the whole array, remembering the first and last index where the value equals the target. If it never appears, the answer is [-1, -1].
function searchRange(nums, target) {
let first = -1;
let last = -1;
// Scan every index; record the first hit, and keep overwriting the last hit.
for (let i = 0; i < nums.length; i++) {
if (nums[i] === target) {
if (first === -1) first = i; // first time we see the target
last = i; // every later hit pushes last forward
}
}
return [first, last];
}This is O(n), but the prompt requires O(log n) and the array is sorted — equal values sit in one contiguous block. Can we do better?
We want the two ends of that block, and each end is a boundary. The first occurrence is the lower bound: the first index whose value is >= target. The last occurrence is one step before the upper bound: the first index whose value is > target, minus one. So run the same boundary search twice — once for target, once for target + 1 — and bracket the run.
If the lower bound lands past the array or on a value that isn't the target, the target is absent and the answer is [-1, -1].
Walking through the lower-bound search for the first occurrence:
nums = [5, 7, 7, 8, 8, 10], target = 8
Lower bound of 8 in [0, 6). nums[3] = 8 is a candidate first occurrence — keep it.
Now [0, 3). nums[1] = 7 is below 8, so the first 8 is to the right — push lo past it.
nums[2] = 7 is still below 8 — the first 8 must be at index 3.
First occurrence is index 3. A second search for 9's lower bound returns 5, so last = 5 − 1 = 4.
Optimization
Two binary searches (lower and upper bound)
Run a lower-bound binary search for the first index whose value is >= target. If that index is out of range or doesn't hold target, the value is absent — return [-1, -1]. Otherwise run an upper-bound search for the first index whose value is > target; the last occurrence is one before it.
O(log n) time, O(1) space.
function searchRange(nums, target) {
const lowerBound = (t) => {
let lo = 0;
let hi = nums.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] < t) lo = mid + 1;
else hi = mid;
}
return lo;
};
const first = lowerBound(target);
if (first === nums.length || nums[first] !== target) return [-1, -1];
const last = lowerBound(target + 1) - 1;
return [first, last];
}Complexity analysis
Time complexity: O(log n). Here's why:
- Finding the first occurrence is one boundary binary search over
nelements — O(log n). - Finding the last occurrence is a second boundary search (the lower bound of
target + 1) — also O(log n).
Two O(log n) searches add to O(log n) overall.
Space complexity: O(1). Here's why:
- Each search keeps only its
lo/hibounds; the two are run one after another, not nested.
The two-element result array is the output, not auxiliary space — overall O(1).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [], target = 1 | [-1,-1] | Empty array — the target is absent. |
| nums = [4], target = 4 | [0,0] | Single matching element — first and last are the same index. |
| nums = [3,3,3,3,3], target = 3 | [0,4] | All equal to the target — the run spans the whole array. |
| nums = [1,5,9], target = 4 | [-1,-1] | Target falls in a gap between values — absent. |
| nums = [1,1,2,2,2,9], target = 2 | [2,4] | Duplicates — brackets the block of 2s from index 2 to 4. |
| nums = [10,20], target = 5 | [-1,-1] | Smaller than every element — absent. |
Try it yourself
Write your solution against the real judge before checking the reference.