For this activity, you will improve insertion sort by including a divide and conquer technique. Follow the instructions:

Using the "divide and conquer" programming technique write a program that implements the binary search algorithm in C$++$ according to the following specifications:

The signature of the function must be: int binary$\_$search $($int $A[],$ int $n,$ int a$).$

A$[]$ is an array of integers

a is an integer, the length of the array.

The returning value is the index of the element in A $.$ If not found, return the index where it should be found. Exmaples:

$2$

$1$

Implement the function void binary$\_$insertion$\_$sort$($int A$[],$ int n$).$

A$[]$ is the array to be sorted.

n is the length of the array.

A $[]$ will be sorted after execution.

Add these implementations and any auxiliar functions in the HW$1.$cpp file. Add also the HW$1.$h file woth the headers of these functions.

Add a test.cpp file having the main function calling and testing your implementation of binary$\_$insertion$\_$sort. Perform tests of your solution in this file.