Find First and Last Position of Element in Sorted Array

This problem challenges you to efficiently locate the starting and ending positions of a target element within a sorted array. Finding these positions is a common task in binary search applications and is useful for tasks like determining the frequency of an element or identifying a range of values. Your solution should be optimized for performance, leveraging the sorted nature of the input array.

Problem Description

Given a sorted array of integers nums and an integer target, find the first and last position of the target in nums. If the target is not found in the array, return [-1, -1].

What needs to be achieved:

Implement an algorithm that identifies the index of the first occurrence and the index of the last occurrence of the target value within the sorted array nums.
Return these two indices as a list or array.
If the target is not present, return [-1, -1].

Key Requirements:

The input array nums is guaranteed to be sorted in ascending order.
The algorithm should be efficient, taking advantage of the sorted nature of the array.
The solution should handle cases where the target appears multiple times consecutively.

Expected Behavior:

The function should return a list/array of two integers representing the first and last positions of the target element. If the target is not found, it should return [-1, -1].

Edge Cases to Consider:

Empty input array nums.
target is smaller than the smallest element in nums.
target is larger than the largest element in nums.
target appears only once in nums.
target appears multiple times consecutively in nums.
nums contains duplicate elements other than the target.

Examples

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Explanation: The first occurrence of 8 is at index 3, and the last occurrence is at index 4.

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Explanation: The target 6 is not found in the array.

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]
Explanation: The input array is empty, so the target cannot be found.

Example 4:

Input: nums = [1], target = 1
Output: [0,0]
Explanation: The target appears only once at index 0.

Constraints

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
nums is sorted in non-decreasing order.
The time complexity of your solution should be O(log n), where n is the length of the array. A brute-force O(n) solution will not be accepted.

Notes

Consider using binary search to efficiently locate the first and last positions. You can perform two binary searches: one to find the first occurrence and another to find the last occurrence. Think about how to modify the standard binary search algorithm to achieve this. The key is to adjust the search boundaries based on whether the middle element is equal to, less than, or greater than the target.