Find First and Last Position of Element in Sorted Array
Medium · Binary Search · Array · Binary Search
Problem
nums is sorted in non-decreasing order, so equal values sit next to each other. Return [first, last]: the first and the last index at which target appears. If it does not appear, return [-1, -1].
The search must take O(log n) time, even when target fills most of the array. Finding one copy and walking left and right from it is not enough: with a hundred thousand copies, that walk is a hundred thousand steps.
Examples
Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]
The two 8s sit at indices 3 and 4.
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
6 would go between the 5 and the first 7, but it is not there.
Constraints
- 0 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- nums is sorted in non-decreasing order
- -10^9 <= target <= 10^9
Approaches
- Find a copy, then walk outwards — time O(log n + k), O(n) worst case, space O(1)
Related problems
Start free on Cariara · Coding problems · System design studio
