Write a recursive implementation of the binary search algorithm (chapter 24.2 in the zyBook) which handles sorted arrays of integers that can contain duplicates. Because duplicate integers may be present in the array, this binary search implementation should be able to handle the case in which the key is present multiple times in the array. To handle this situation, your implementation will return a range of indices in the array corresponding to the key instead of just a single index.

For example, if the input array is [1,2,2,2,5], and the key is 2, the binary search implementation will return the range [1,3], representing the starting index of 1 and the ending index of 3 for the key.

For the case in which the key is present only once in the array, your implementation will still return two values, but they will be the same. For example, if the input array is [1,2,5], and the key is 2, your binary search implementation will return the range [1,1], representing the starting index of 1 and the ending index of 1 (single match) for the key.

If the key is not present in the array, then your binary search implementation will return -1 for the start index and end index (will return the range [-1,-1]).

Your implementation will be written in a class called Main, and will contain a method called binarySearch with the following declaration:

public static int[] binarySearch(int[] nums, int key)

This method has two parameters, nums, which is the sorted array of integers, and key, which is the integer being searched for in the array. The return type is an integer array of size 2, representing the starting index and the ending index of the integers matching the key. Implementation Requirements Your implementation must follow these requirements:

The binary search implementation must be recursive. Hint: create a private static method which provides the recursion, and call it from your binarySearch method with the initial arguments.

You cannot use any loop structures (for, while, etc) in your implementation. Hint: think about the problem as finding the start index of the key first, and then finding the end index after the start index has been computed.

You cannot use any class fields. This means that any values you need to 'remember' between recursive calls should be passed as local arguments to the recursive method itself.

Code comments must be present. There are no rules on how many comments should be present, but do not submit code without any comments.

Examples In the following examples, the input corresponds to the arguments to the binarySearch method, and the output is the array returned by the method. You do not need to actually output anything; the test cases will call your binarySearch method directly. You only need to return an array with the start / end indices.

Given input: nums = [5,7,7,11], key = 7

output is:

return = [1,2]

The example above shows the result when the input contains duplicate values which match the key. Because the array is sorted, duplicate values will always be next to each other.

Given input: nums = [5,8,12], key = 8

output is:

return = [1,1]

Because the key (in this example 8) only has one match in the nums array, the start and end indices are the same. Your method will always return an integer array of size 2 even if there is only one match.

Given input: nums = [5,5,7,7,9,11,11], key = 8

output is:

return = [-1,-1]

When the key is not found in the nums array, your method will return -1 for both the start and end index.