Write one C++ function for the Binary Search algorithm based on the pseudocode in the textbook on page 396. to search a target element in a sorted, ascending or descending, order vector. Your function should also keep track of the number of comparisons used to find the target.

(a) (5 points) To ensure the correctness of the algorithm the input data should be sorted in ascending or descending order. An exception should be thrown when an input vector is unsorted.

(b) (10 points) Test your program using vectors populated with:

i. consecutive increasing integers in the ranges from 1 to powers of 2, that is, to these numbers: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048. Select the target as the last integer in the vector.

ii. consecutive decreasing integers in the ranges from powers of 2 to 1 , that is, to these numbers: 2048, 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1. Select the target as the last integer in the vector

Textbook: https://o6ucs.files.wordpress.com/2012/11/data-structures-and-algorithms-in-c.pdf

Q OO 396 (420 of 738) 10096 1) 396 (420 of 738) mid-(low +high)/2]. We consider three cases: If k e.key(), then we have found the entry we were looking for, and the search terminates successfully returning e If k e.key(), then we recur on the first half of the vector, that is, on the range of indices from low to mid - 1 If k e. key(), we recur on the range of indices from mid+ 1 to high This search method is called binary search, and is given in pseudo-code in Code Fragment 9.18. Operation find(k) on an n-entry map implemented with an ordered vector L consists of calling BinarySearch(L,k,0,n-1) Algorithm BinarySearch(L,k, low,high) Input: An ordered vector L storing n entries and integers low and hig.h Output: An entry of L with key equal to k and index between low and high, if if low > high then else such an entry exists, and otherwise the special sentinel end return end mid-L(low + high) /2] e L.at(mid) if k=e.key() then return e else if ke.key() then return BinarySearch(L,k,low,mid -1) else return BinarySearch(L.k,mid+1,high) Code Fragment 9.18: Binary search in an ordered vector