Find a Peak Element in an array

Given an array of size n, find a peak element in the array. Peak element is the element which is greater than or equal to its neighbors.
For example – In Array {1,4,3,6,7,5}, 4 and 7 are peak elements. We need to return any one peak element.

Algorithm

Linear approach:
One way to solve this problem is to iterate over the array and find an element that is greater than or equal to its neighbors and return it.
Time Complexity: O(n)
Efficient approach:
1. Initialize start = 0, end = array.length – 1
2. Repeat following steps till peak element is found:
a). Find mid = (start+end)/2
b). If array[mid] is peak element, return array[mid]
c). Else if array[mid-1] > array[mid], find peak in left half of array
set end = mid – 1
d). Else find peak in right half of array
set start = mid + 1
Time Complexity: O(log n)

 

Code->

int findPeakUtil(int arr[], int low, int high, int n)
{
// Find index of middle element
int mid = low + (high - low)/2; /* (low + high)/2 */

// Compare middle element with its neighbours (if neighbours exist)
if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
(mid == n-1 || arr[mid+1] <= arr[mid]))
return mid;

// If middle element is not peak and its left neighbour is greater
// than it, then left half must have a peak element
else if (mid > 0 && arr[mid-1] > arr[mid])
return findPeakUtil(arr, low, (mid -1), n);

// If middle element is not peak and its right neighbour is greater
// than it, then right half must have a peak element
else return findPeakUtil(arr, (mid + 1), high, n);
}

// A wrapper over recursive function findPeakUtil()
int findPeak(int arr[], int n)
{
return findPeakUtil(arr, 0, n-1, n);
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *

For Inserting code :
Paste your code in the comment form, select it and then click the language link

C | C++ | Java |

*