$15\mathrm{.}12$ 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:

the output is:

index: $1,$ recursions: $2,$ comparisons: $31$:Compare output

$-$Input

$9$

$123456789$

$2$

Expected output

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

$-$Input

$9$

$112233445566778899$

$11$

Expected output

index: $0,$ recursions: $3,$ comparisons: $5$

$-$Input

$9$

$112233445566778899$

$99$

Expected output

index: $8,$ recursions: $4,$ comparisons: $7$

$-$Input

$8$

$1015202530354045$

$50$

Expected output

index: $-1,$ recursions: $4,$ comparisons: $7$