In c$++$ please!! $15\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 function BinarySearch$()$ with the following specifications:

Parameters:

a target integer

a vector of integers

lower and upper bounds within which the recursive call will search

Return value:

the index within the vector where the target is located

$-1$ if target is not found

The template provides the main program and a helper function that reads a vector from input.

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

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

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

Otherwise call the function recursively on half the vector parameter:

If integers.at$($index$)$ target, search the vector from index $+1$ to upper

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

The vector 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 vector. Note: lower $==$ upper should not be counted.

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

The input of the program consists of:

the number of integers in the vector

the integers in the vector

the target to be located

Ex: If the input is:

$9$

$123456789$

$2$

the output is:

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

$537614\mathrm{.}4094172.$qx$3$zqy$7$

Instructor note:

Line $32$ here uses notation from C$,$ as opposed to C$++-$ printf is the C equivalent of using the cout function in C$++.$

The "translated" line would look like:

cout $$ "index: $"$ index recursions: $"$ recursions comparisons: $"$ comparisons $$ endl; #include

#include

#include

using namespace std;

$//$ Read integers from input and store them in a vector.

$//$ Return the vector.

vector ReadIntegers$()\{$

int size;

cin $>>$ size;

vector integers$($size$)$;

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

cin $>>$ integers.at$($i$)$;

$\}$

sort$($integers$.$begin$(),$ integers.end$())$;

return integers;

$\}$

int BinarySearch$($int target, vector integers, int lower, int upper$)\{$

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

$\}$

int main$()\{$

int target;

int index;

vector integers $=$ ReadIntegers$()$;

cin $>>$ target;

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

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

$",$

index, recursions, comparisons$)$;

return $0$;

$\}$