# Peak element in an array

Given an array. we should Find a peak element in it. An array element is a peak if it is not smaller than its neighbours. For corner elements, we need to consider only one neighbour.

**Example:**

Input: array[]= {5, 10, 20, 15}

Output: 20

The element 20 has neighbours 10 and 15,

both of them are less than 20.

Input: array[] = {10, 20, 15, 2, 23, 90, 67}

Output: 20 or 90

The element 20 has neighbours 10 and 15,

both of them are less than 20, similarly, 90 has neighbour 23 and 67.

**method 1:**

__ Naive Approach:__ The array can be traversed and the element whose neighbours are less than that element can be returned.

- the first element is greater than the second or the last element is greater than the second last, than print that particular element
- Else traverse the array from the second index to the second last index
- If for an element array[i], it is greater than both its neighbours, i.e., array[i] > array[i-1] and array[i] > array[i+1], then print that element.

int peakElement(int arr[], int n){if (n == 1)return arr[0];if (arr[0] >= arr[1])return 0;if (arr[n - 1] >= arr[n - 2])return n - 1;for (int i = 1; i < n - 1; i++)

{if (arr[i] >= arr[i - 1] && arr[i] >= arr[i + 1])return i;}}

**Complexity Analysis:**

**Time complexity:**O(n).**Space Complexity:**O(1).

__method 2__: divide and conquer approach

- Create two variables,
*l*and*r*, initilize*l = 0*and*r = n-1* - Iterate the steps below till
*l <= r*, lowerbound is less than the upperbound - Check if the mid value or index
*mid = (l+r)/2*, is the peak element or not, if yes then print the element and terminate. - Else if the element on the left side of the middle element is greater then check for peak element on the left side, i.e. update
*r = mid – 1* - Else if the element on the right side of the middle element is greater then check for peak element on the right side, i.e. update
*l = mid + 1*

int findPeakUtil(int arr[],int low,int high, int n){int mid=(low+high)/2;if ((mid == 0 || arr[mid - 1] <= arr[mid]) &&(mid == n - 1 || arr[mid + 1] <= arr[mid]))return mid;else if (mid > 0 && arr[mid - 1] > arr[mid])return findPeakUtil(arr, low, (mid - 1), n);elsereturn findPeakUtil(arr, (mid + 1), high, n);}int peakElement(int arr[], int n){return findPeakUtil(arr, 0, n - 1, n);}

**Complexity Analysis:**

**Time Complexity: O(Logn).****Space complexity: O(1).**