Reference no: EM132093992

Please answer all parts of the following in a detailed and easy to read manner. Thank you :).

Original array: 2, 3, 5, 8, 9, 10, 14, 18, 28, 30

Sorted, but rotated array: 8, 9, 10, 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 fo 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 66.

Incidentally, the pivot also happens to be the largest element in the array and is the lasat 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 an 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).