Find first and last positions of an element in a sorted array
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]
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];}