Find first and last positions of an element in a sorted array

Medium

Problem

Given an array sorted in ascending order (it may contain duplicates) and a target, return the first and last indices of the target, or [−1, −1] if it is absent. Use 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]

Test cases

Case 1

Input:    [5,7,7,8,8,10], 8
Expected: [3,4]

Case 2

Input:    [5,7,7,8,8,10], 6
Expected: [-1,-1]

Case 3

Input:    [], 0
Expected: [-1,-1]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Two binary searches (lower / upper bound)

Time O(log n)Space O(1)

One search for the leftmost index ≥ target, another for the leftmost index > target.

function searchRange(nums, target) {
const bound = (isLower) => {
let lo = 0, hi = nums.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (nums[mid] > target || (isLower && nums[mid] === target)) hi = mid;
else lo = mid + 1;
}
return lo;
};
const first = bound(true);
if (first === nums.length || nums[first] !== target) return [-1, -1];
return [first, bound(false) - 1];
}