Array Counting Binary Search
Intermediate Level

Implement the searchRangeOfTarget method that returns the first and last position of a target in a sorted array.

The input contains a sorted integer array nums, its length size, and an integer target. Your task is to return the first and last index where target appears.

If the target does not exist in the array, return [-1,-1]. For example, in [5,7,7,8,8,10], the target 8 starts at index 3 and ends 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[]) = [2,2]
size (int) = 2
target (int) = 2
Return:
(int[]) [0,1]

Use binary search twice.

The first binary search finds the leftmost occurrence of the target by continuing to search on the left side after a match. The second binary search finds the rightmost occurrence by continuing to search on the right side after a match.

Return both indexes together.

Pseudocode:

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