The integer array nums is sorted from smallest to largest, and the same value may appear several times in a row. Return [first, last]: the index where target first appears and the index where it last appears. If target is not in nums at all, return [-1,-1].
Try to do it in O(log n) time.
The three 3s fill indices 1, 2 and 3.
5 would sit between the 4s and the 8, but it is not there.
A value that appears once starts and ends at the same index.
Constraints
0 <= nums.length <= 10⁵ (nums may be empty)-10⁹ <= nums[i] <= 10⁹nums is sorted in non-decreasing order.-10⁹ <= target <= 10⁹A plain binary search stops at some copy of target, not necessarily the first or last. Ask a sharper question instead: what is the first index whose value is at least target?
Because nums is sorted, all copies of target sit next to each other in one run. The answer is the two ends of that run.
Time O(log n)Space O(1)
The full walkthrough and code are part of Premium