Write in C++ a non-templated iterative binary search algorithm which searches a vector of N integers for an integer key. Write in C++ a template version of a recursive binary search function to search a vector. Specify requirements on the template parameter type. Discuss as comments the requirements on the template parameter type. template int bSearch(vector vec, int first, int last, I value) { if (last >= first) { int mid = first + (last first) / 2; // If the element is present at the middle itself if (vec[mid] == value) return mid; // If element is smaller than mid, then it can only be present // in left subarray if (vec[mid] > value) return bSearch(vec, first, mid - 1, value);| // Else the element can only be present in right subarray return bSearch(vec, mid + 1, last, value); } // We reach here when element is not present in array return -1; Question Now fill the vector with N random integers, then searching the vector X times for a random integer in the range 0..N. N=10,000,000 and X = 10,000 Output the average search time (wall and CPU times) Note: you can use the type unsigned long long int for N Write in C++ a non-templated iterative binary search algorithm which searches a vector of N integers for an integer key. Write in C++ a template version of a recursive binary search function to search a vector. Specify requirements on the template parameter type. Discuss as comments the requirements on the template parameter type. template int bSearch(vector vec, int first, int last, I value) { if (last >= first) { int mid = first + (last first) / 2; // If the element is present at the middle itself if (vec[mid] == value) return mid; // If element is smaller than mid, then it can only be present // in left subarray if (vec[mid] > value) return bSearch(vec, first, mid - 1, value);| // Else the element can only be present in right subarray return bSearch(vec, mid + 1, last, value); } // We reach here when element is not present in array return -1; Question Now fill the vector with N random integers, then searching the vector X times for a random integer in the range 0..N. N=10,000,000 and X = 10,000 Output the average search time (wall and CPU times) Note: you can use the type unsigned long long int for N