Complete and full answer in order to give creditThank you An

Complete and full answer in order to give credit.Thank you.

An array A of n distinct numbers are said to be unimodal if there exists an index k, 1 k n, such that A[1] < A[2] < · · · < A[k 1] < A[k] and A[k] > A[k + 1] > · · · > A[n]. In other words, A has a unique peak and are monotone on both sides of the peak. Design an efficient algorithm that finds the peak in a unimodal array of size n.

Solution

This problem can be solved by implementing binary search divide and conquer method in our algorithm.

1. Algorithm peak( low, high )

2. {

3. if( high = low)

4. { // if there is only one element in the array, it is the peak vaue.

5. return a[low];

6. }

7. else

8. {

9. mid := (low + high) / 2;

10. if ( a[mid-1] < a[mid] && a[mid+1] < a[mid] ) then return a[mid]; // condition for peak value.

11. else if (a[mid-1] <a[mid] && a[mid+1] > a[mid] ) then // if peak is to the right of mid value in array.

12. return peak( mid+1,high);

13. else return peak(low,mid-1); // if peak is to the left of mid value in array.

14. }

15. }

The algorithm above, has a time complexity of O( 1 ) for the best case, i.e, only one element in array,

average and worst case time complexity is O( log n ) , as the array is decremented by a factor of 2.