Find peak element in array implementation

Find peak element in array

Today’s problem is to find peak element in array. A peak element is defined as an element which is not smaller than its neighbors.Mathematically, ith element is called as peak following property holds true:
find peak element in array

For first element and last elements of array, left and right neighbors respectively, are considered as negative infinity. Given an input array with non sorted integers, find peak element in it. For an array which is all sorted elements, last element will be peak. For an array which is all reversed sorted elements, first element will be peak.

Methods to find peaks in array

Simple approach would be to scan through array and for every element, check for the above mentioned property. As soon as some element satisfy the condition, return the index.

In worst case we would end up scanning whole array (in case array integers are all sorted), which will give us complexity of O(N). Can we do better than this?

If a given number is not peak, there are two cases:
1. Either we are rising towards right, that means A[i+1] > A[i]
2. Or we are falling from left, that means A[i-1] > A[i].

With above two cases, we can safely say that in first case, there would be some peak in right sub array and in second case there would be some peak in left sub array. How come?

Let’s say we divide the whole array in two parts, having m and n elements each.

X = A[0], A[1], ........A[m-1], A[m]
Y = A[m+1], A[m+2]..........A[n-1]

If A[m] > A[m-1] && A[m] > = A[m+1], mth element is peak element, return it.

Now if A[m] < A[m+1], i.e last element of X is less than first element of Y. In that case, there is possibility that either A[m+1] is peak, or some subsequent element would be.In worst case it would be the last element.

If A[m] < A[m-1], that is last element of X is less that second last element of X. In that case, either A[m-1] is peak or some element preceding it would surely will be. In worst case, first element will be the peak. 
Now question is how to select m? Let’s do it with binary search which will reduce our complexity to O(log N).

Find peaks in array implementation

int findPeakElement(int a[], int start,int size){

        int mid =  (start + size)/2;

        if((mid == 0 || a[mid] > a[mid-1]) &&
            (mid == size-1 || a[mid] > a[mid+1])){
                return mid;
        }
        else if(a[mid] < a[mid+1])
                return findPeakElement(a,mid+1, size);
        else
                return findPeakElement(a,0, mid-1);
}

Complexity of algorithm to find peak element in array is is O(log N).

Please share if there is something wrong or missing. If you want to contribute to algorithms and me, please contact us.