we have an array A1n with this features if m

we have an array : A[1...n]

with this features:

if m <= i < 1 then A[i] < A[i+1]

if m < i <= n then A[i] > A[i+1]

It\'s clear that A[m] is the maximum element of array.

I want an efficient algorithm to find the maximum element of the array and calculate the order of the algorithm.

Solution

Consider array and then divide it into n/5 lists such that it consists of 5 elements in each and every list. Let us calculate the median in each and every sub array. then let us calculate median by considering all the medians, and name it as M Now let us Divide the array into two sub arrays .The first sub-array must have the elements greatet than M ,and it can be named as a1 , on the other hand the sub-array consists of the elements smaller than M.,and it is named as a2. If b <= |a1|, return selection (a1,b). If b 1 = |a1|, result is M. If b> |a1| + 1, then return selection(a2,b a1 1).