Fix my coding In c$++$ please!! almost all of it is right but for some outputs its wrong. $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;

int recursions $=0$; $//$ Global variable to count the number of recursive calls

int comparisons $=0$; $//$ Global variable to count the number of comparisons

vector ReadIntegers$()\{$

int size;

cin $>>$ size;

vector integers$($size$)$;

for $($int i $=0$; i $$ size; $++$i$)\{$

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

$\}$

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

return integers;

$\}$

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

$++$recursions; $//$ Increment recursion count

if $($lower $>$ upper$)$ return $-1$; $//$ Target not found

$//$ Increment comparison count

int mid $=($lower $+$ upper$)/2$;

if $($target $==$ integers$[$mid$])\{$

comparisons$++$; $//$ Increment comparison count

return mid;

$\}$; $//$ Target found at midpoint if $($target $$ integers$[$mid$])\{$

comparisons$++$; $//$ Increment comparison count

return BinarySearch$($target$,$ integers, lower, mid$-1)$; $//$ Search lower half

$\}$ else $\{$

comparisons$++$; $//$ Increment comparison count

return BinarySearch$($target$,$ integers, mid $+1,$ upper$)$; $//$ Search upper half

$\}$

$\}$

int main$()\{$

int target, index;

vector integers $=$ ReadIntegers$()$;

cin $>>$ target;

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

cout $$ "index: $"$ index recursions: $"$ recursions comparisons: $"$ comparisons$+1$ endl;

return $0$;

$\}$