First and Last Occurrence

You are given an integer array nums sorted in non-decreasing order, and an integer target. Because the array is sorted, every copy of target occupies one contiguous block of indices.

Return the first and last index of that block as a two-element array [first, last]. If target does not appear in nums at all, return [-1, -1].

The array may be empty, in which case the answer is [-1, -1].

You must write an algorithm with $O(\log n)$ runtime complexity.

Examples

Example 1

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Explanation: The value 8 occupies indices 3 and 4, so the first index is 3 and the last is 4.

Example 2

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Explanation: The value 6 never appears; index 1 is the first position where a 6 could be inserted, but nums[1] is 7.

Example 3

Input: nums = [], target = 0
Output: [-1,-1]
Explanation: There is nothing to search, so the answer is [-1,-1].