$14\mathrm{.}33\mathrm{.}1$: 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 integeran ArrayList of integerslower 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 upperIf 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:

$91234567892$

the output is:

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

SOLVE USING THIS FORMAT PLEASE

import java.util.Scanner;

import java.util.ArrayList;

import java.util.Collections;

public class LabProgram $\{$

$//$ Read and return an ArrayList of integers.

$$private static ArrayList readNums$($Scanner scnr$)\{$

$$ int size $=$ scnr$.$nextInt$()$; $//$ Read size of ArrayList

$$ ArrayList nums $=$ new ArrayList$()$;

$$ for $($int i $=0$; i $<$ size; $++$i$)\{//$ Read the numbers

$$nums$.$add$($scnr$.$nextInt$())$;

$\}$

$$ return nums;

$\}$

$$static public int binarySearch$($int target, ArrayList integers,

$$ int lower, int upper$)\{$

$/*$ Type your code here. $*/$

$\}$

$$public static void main$($String $[]$ args$)\{$

$$ Scanner scnr $=$ new Scanner$($System$.$in$)$;

$//$ Input a list of integers

$$ ArrayList integers $=$ readNums$($scnr$)$;

$//$ Input a target value for the search

$$ int target $=$ scnr$.$nextInt$()$;

$$ int index $=$ binarySearch$($target$,$ integers, $0,$ integers.size$()-1)$;

$$ System.out.printf$("$index: $\%$d$,$ recursions: $\%$d$,$ comparisons: $\%$d

$",$

$$ index, recursions, comparisons$)$;

$\}$

$\}$