Array Sorting Binary Search Two Pointers
Intermediate Level

Implement the firstAndLastPositionBinary method that returns the first and last target positions using binary search.

The input contains a sorted integer array nums, its length size, and a target value.

Your task is to return an array containing the first and last index where target appears. If the target is not present, return [-1,-1].

For example, in [5,7,7,8,8,10], the value 8 first appears at index 3 and last appears at index 4.

Example 1
Input:
nums (int[]) = [5,7,7,8,8,10]
size (int) = 6
target (int) = 8
Return:
(int[]) [3,4]
Example 2
Input:
nums (int[]) = [5,7,7,8,8,10]
size (int) = 6
target (int) = 6
Return:
(int[]) [-1,-1]
Example 3
Input:
nums (int[]) = [1]
size (int) = 1
target (int) = 1
Return:
(int[]) [0,0]

Use binary search two times.

The first binary search looks for the leftmost occurrence of the target. When the target is found, store the index and continue searching on the left side.

The second binary search looks for the rightmost occurrence. When the target is found, store the index and continue searching on the right side.

Pseudocode:

function findBoundary(nums, size, target, findFirst):
    left = 0
    right = size - 1
    answer = -1
    while left <= right:
        mid = left + (right - left) / 2
        if nums[mid] == target:
            answer = mid
            if findFirst:
                right = mid - 1
            else:
                left = mid + 1
        else if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return answer
function firstAndLastPositionBinary(nums, size, target):
    first = findBoundary(nums, size, target, true)
    last = findBoundary(nums, size, target, false)
    return [first, last]
Run your code to see the result.