Make delicious recipes!

Find a peak element



Problem: A peak element is defined as an element which is NOT smaller than its immediate neighbors.
Two exceptions to a peak element are:
    First element is a peak element if its not smaller than second element.
    Last element is a peak element if its not smaller than second-last element.
For an array with all elements equal, all elements are peak elements.


Example: Peak elements in [5, 7, 3, 9, 10, 12] are 7 and 12



Solution: An O(n) solution for this problem is very easy.
Just loop over the elements of the array and if any element satisfies the peak element's condition, then return it.

However, this can be converted into a binary search (without the array being sorted) if we observe the following:

If an element is not the peak, then that element must be smaller than one of its neighbors.
If left neighbor is greater, then left half of the array must have a peak.
Similarly, if right neighbor is greater, then right half of the array must have a peak.


This can be used to divide our search for peak element into half every time we analyze an element for being the peak.

Code:


int findPeak(int arr[])
{
    return findPeak (arr, 0, arr.length-1);
}


int findPeak (int arr[], int low, int high)
{
     
    int mid = low + (high - low)/2;  // same as (low + high)/2 but prevents overflow
 
    // check starting boundary
    if (mid == 0 && arr[mid+1] <= arr[mid])
        return mid;

    // check ending boundary
    if (mid == arr.length-1 && arr[mid-1] <= arr[mid])
        return mid;
 
    // check presence of peak at the current mid
    boolean leftSmaller = arr[mid-1] <= arr[mid];
    boolean rightSmaller = arr[mid+1] <= arr[mid];

    if (leftSmaller && rightSmaller)
        return mid;

    /* Middle is not a peak, recurse to find the peak */
    /* Below recursion eliminates one half at every step */
    /*  and that's how it becomes log(N) */

    // If left neighbor is greater than current mid, 
    // then peak must be present in the left half
    if (leftSmaller==false && mid>0)
        return findPeak (arr, low, (mid -1));
 
    // If right neighbor is greater than current mid, 
    // then peak must be present in the right half
    else return findPeak (arr, (mid + 1), high);
}





This code is log(N) because at every recursive call, it eliminates one-half of the array.

Also note that the above code finds just one peak. To find all the peaks, recurse in both the halves.
But that would make this code O(N) again and in that case, its better to go for plain looping solution with the same complexity.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal