An array A1 n is unimodal if its consists of an increasin

An array A[1 . . . n] is unimodal if its consists of an increasing sequence followed by a decreasing sequence. More precisely, there exists an index k {1, 2, . . . , n} such that

• A[i]<A[i+1]for all ai<k,and

• A[i]>A[i+1] for all ki<n.

Give an algorithm to compute the maximum element of a unimodal input array A[1...n] in O(logn) time. Argue for the correctness of your algorithm by presenting the loop invariant(s) that your algorithm maintains and show why they lead to the correctness of your algorithm. Finally, prove the bound on its running time.

Solution

Algorithm:

Unimodal(array[1..n],i,k,n):

     //In this algorithm we are going to calculate middle element and checking their neighbouring elements if condition not satisfy then again calculating middle element of first half or second half.

mid=(1+n)/2

if(array[mid]>=arr[mid-1] and array[mid]>=array[mid+1]):

    return array[mid]

end if

if(array[mid]<arr[mid-1] and array[mid]>array[mid+1]):

    return unimodal(array[1..n],1,k,mid)

else //(arrray[mid]>array[mid-1] and array[mid]<array[mid+1]):

    return unimodal(array[1...n],mid,k,n)

The above algorithms executes in O(log n) time,since we are calculating middle term and eliminating half of the array for cheking each time,and get answer in log n time.

The above algorithm return the maximum element from the array.