Find First and Last Position of Element in Sorted Array
The key idea
Run binary search twice. The first search finds the leftmost index where
target could go (the lower bound); the second finds the leftmost index where target + 1 could go, minus one (the upper bound). If the lower bound holds target, the pair is the answer; otherwise target is absent and the answer is [-1, -1].Problem
Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
If target is not found in the array, return [-1, -1].
You must write an algorithm with O(log n) runtime complexity.
Constraints
0 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^9numsis a non-decreasing array.-10^9 <= target <= 10^9
Examples
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Input: nums = [], target = 0
Output: [-1,-1]
Complexity
Time: O(log n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Binary Search problems
- Binary SearchEASY
- Capacity To Ship Packages Within D DaysMEDIUM
- Find in Mountain ArrayHARD
- Find K Closest ElementsMEDIUM
- Find Minimum in Rotated Sorted ArrayMEDIUM
- Find Peak ElementMEDIUM
- First Bad VersionEASY
- Guess Number Higher or LowerEASY
- Koko Eating BananasMEDIUM
- Lowest Common Ancestor of a Binary Search TreeMEDIUM
- Median of Two Sorted ArraysHARD
- Search a 2D MatrixMEDIUM