# 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); }