Theory Review: a) Linear Search: The linear search approach compares the key element key sequentially with each element in the array. It continues to do so until the key matches an element in the array or the array is exhausted without a match being found. If a match is made, the linear search returns the index of the element in the array that matches the key. If no match is found, the search returns -1. Code for Linear Search Method int linearSearch (int array[], size, int key) { for (int i = 0; i < size; i++) { if (key array[i]) } return i; //If found, return index of that element return -1; //if not found, return -1 } b) Binary Search: Binary search is the other common search approach for a list of values. For binary search to work, the elements in the array must already be ordered. Assume that the array is in ascending order. The binary search first compares the key with the element in the middle of the array. Consider the following three cases: If the key is equal to the middle element, the search ends with a match. If the key is less than the middle element, you need to continue to search for the key only in the first half of the array. If the key is greater than the middle element, you need to continue to search for the key only in the second half of the array. Clearly, the binary search method eliminates at least half of the array after each comparison. Code for Binary Search Method int binarySearch (int array [], int size, int key) int low 0, high size-1, mid = 0; while (low <- high) { } mid (low + high)/2; if (key array[mid]) return mid; else if (key <array [mid]) // change high high mid-1; else change low low mid + 1; return -1; // if key not found above LAB EXERCISE: 1. Create a new project with the name Lab2_SearchingMethods. Inside this project, create a file with the name Search Methods. 2. In SearchMethods file create the following methods: ⚫fillArray() method, to initialize the array with random values (between 0 and 100 million) void fillArray (int array[]) { for (int i = 0; i < size; i++) { array[i] (rand() %size); linearSearch() method which finds the element in an array using linear search approach and returns its index to the calling main method, otherwise it returns -1. binarySearch() method which finds the element in an array using binary search approach and returns its index to the calling main method, otherwise it returns -1. In main() method, Create test Array: int test [10000000]; Fill the elements in the test array, by calling fill Array(test) method. Ask the user to enter a key to search for it in the test array, by calling the linearSearch(test, key), and binarySearch (test,key). You should tell the user if or not the key is found Compute the running time of two searching methods in seconds. Note Before calling the binarySearch() method, you must sort the test array by do two things: include <algorithm> header and invoke sort(test, test + size) -To compute the running time, you need to get the time immediately before the search and then immediately after the search by using clock() which returns the processor time consumed by the program. clock_t start = clock(); statements.... clock_t stop clock(); = double totalTime (double(stop)-double(start))/CLOCKS_PER_SEC;