Q2: 25 points) Consider a sorted, but rotated array of distinct integers (i.e., no two integers are the same). For example, the following sorted array 2 3 509 10 14 18 20 302 3 6 9 10 14 18 29 30 2 3 5 89 10 14 18 2830 when rotated three elements to the "left" becomes: 8910 14 18 28 30 2 3 5 All the elements (except an element called the pivot at index p) of the sorted, but rotated array of integers have a property that they are less than the element to the right of them. Only the pivot element is greater than the element to the right of it. In the above sorted, but rotated array of integers, the pivot is the integer 30 at index 6. Incidentally the pivot also happens to be the largest element in the array and is the last element in the original sorted array (before the rotation). In the above example, the pivot element 30 is the largest element of the array and is also the last element of the original sorted array (before the rotation). (a) Design a binary search-based algorithm to identify the pivot in a sorted, but rotated array of integers b) Extend the algorithm of (a) to do a successful search for a key that is present in the sorted, but rotated array (c) Extend the algorithm of (a) to do a unsuccessful search for a key that is not present in the sorted, but rotated array d) For each of the algorithms in (a), (b) and (c), illustrate the execution of the algorithm for the array given in the problem statement. (e) Analyze the time complexity of the algorithms of (a), (b) and (c) Note that in addition to describing the working of your algorithms, you should also write the pseudo code for your algorithms of (a), (b) and (c)