$17\mathrm{.}14$ LAB: Binary search

Binary search can be implemented as a recursive algorithm. Each call makes a recursive call on one$-$half of the list the call received as an argument.

Complete the recursive method binarySearch$()$ with the following specifications:

Parameters:

a target integer

an ArrayList of integers

lower and upper bounds within which the recursive call will search

Return value:

the index within the ArrayList where the target is located

$-1$ if target is not found

The template provides main$()$ and a helper function that reads an ArrayList from input.

The algorithm begins by choosing an index midway between the lower and upper bounds.

If target $==$ integers.get$($index$)$ return index

If lower $==$ upper, return $-1$ to indicate not found

Otherwise call the function recursively on half the ArrayList parameter:

If integers.get$($index$)<$ target, search the ArrayList from index $+1$ to upper

If integers.get$($index$)>$ target, search the ArrayList from lower to index $-1$

The ArrayList must be ordered, but duplicates are allowed.

Once the search algorithm works correctly, add the following to binarySearch$()$:

Count the number of calls to binarySearch$().$

Count the number of times when the target is compared to an element of the ArrayList. Note: lower $==$ upper should not be counted.

Hint: Use a static variable to count calls and comparisons.

The input of the program consists of:

the number of integers in the ArrayList

the integers in the ArrayList

the target to be located

Ex: If the input is:

$9$

$123456789$

$2$

the output is:

index: $1,$ recursions: $2,$ comparisons: $3$