In this fourth part of the signature assignment, code is developed for sorting and searching using a binary search algorithm.

Write a function named selection$\_$sort, which takes two parameters: an integer pointer and an integer size. Search the Internet or consult a textbook for an example of selection sort. Add code to implement a selection sort algorithm. Add any needed functions to support the selection sort. The function should sort the array in place and return nothing.

Write a recursive function named binary$\_$search$\_$recursive, which takes four parameters from a helper function. The first is an integer pointer representing the array of values, the second is an integer representing the value to be searched for, the third is an integer for the starting index, and the fourth is an integer for the ending index. The function returns a Boolean value representing if the searched$-$for value was found.

Write a helper function named binary$\_$search that takes three parameters: the first is a pointer to an integer array, the second is the array size, and the third is a searched$-$for value. This function calls the recursive function and passes the array, the search value, the starting index, and the ending index; remember, the size and the ending index are related but not equivalent. The function returns the Boolean value returned by the recursive search function.

Add a new class named SearchAnalyzer, which subclasses Analyzer and implements the analyze method. Use the override keyword appropriately. The constructor should first initialize the base class by calling the Analyzer constructor, then in the constructor body, call the selection$\_$sort function, passing the instance variable values and the size $($do not pass the parameter values and size!$).$ In the analyze method, generate $100$ random integer values from $0$ to $999$ and use the binary$\_$search function to see if that value exists in the data. Count the number of found values and return the count in a std::string.

Modify the StatisticsAnalyzer constructor to call the selection$\_$sort function, passing it the correct argument values. Alter the minimum and maximum values computation, considering the array is now sorted. Add functionality to implement the median and mode averages using the sorted data. The median is the exact middle value if there is an odd number of elements, and the mean of the two middle values is if there is an even number of elements. The mode is the most frequently occurring value; if more than one value occurs with this frequency, pick the first one.

The final main function should look like this:

const int SIZE $=1000$;

int main$()\{$

createBinaryFile$("$binary$.$dat", SIZE$)$;

BinaryReader br$("$binary$.$dat"$)$;

StatisticsAnalyzer sa$($br$.$getValues$(),$ br$.$getSize$())$;

std::cout $<<$ sa$.$analyze$()<<\text{'}$

$\text{'}$;

DuplicateAnalyzer da$($br$.$getValues$(),$ br$.$getSize$())$;

std::cout $<<$ da$.$analyze$()<<\text{'}$

$\text{'}$;

MissingAnalyzer ma$($br$.$getValues$(),$ br$.$getSize$())$;

std::cout $<<$ ma$.$analyze$()<<\text{'}$

$\text{'}$;

SearchAnalyzer ra$($br$.$getValues$(),$ br$.$getSize$())$;

std::cout $<<$ ra$.$analyze$()<<\text{'}$

$\text{'}$;

return $0$;

$\}$

Use these function and class headers:

class SearchAnalyzer : public Analyzer

SearchAnalyzer$($int$*$ values, int size$)$

std::string analyze$()$ override

void selection$\_$sort$($int$*$ values, int size$)$

bool binary$\_$search$\_$recursive$($int$*$ values, int key, int start, int end$)$

bool binary$\_$search$($int$*$ values, int size, int key$)$

Example output:

The minimum value is $0$

The maximum value is $999$

The mean value is $499\mathrm{.}495$

The median value is $497$

The mode value is $81$ which occurred $5$ times

There were $269$ duplicated values

There were $361$ missing values

There were $62$ random values found