Plain binary search stops at any match. When the list contains duplicates you often need the boundaries: where does a run of equal values start and end? The trick is to keep searching even after you hit the target.
Given a list nums sorted in non-decreasing order (duplicates allowed) and an integer target, return [first, last], the indices of the first and last occurrence of target. If the target is absent return [-1, -1].
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]
Constraints
0 <= len(nums) <= 10**4- Aim for O(log n) time. A linear scan is O(n) and misses the technique; do not use the
bisectmodule.
Goals
- Adapt binary search to keep going after finding a match
- Find the leftmost boundary and the rightmost boundary as two separate searches
- Reason about which side mid belongs to when nums[mid] equals the target