# Find a peak element

Given an array of integers. Find a peak element in it. An array element is peak if it is NOT smaller than its neighbors. For corner elements, we need to consider only one neighbor. For example, for input array {5, 10, 20, 15}, 20 is the only peak element. For input array {10, 20, 15, 2, 23, 90, 67}, there are two peak elements: 20 and 90. Note that we need to return any one peak element.

Following corner cases give better idea about the problem.
1) If input array is sorted in strictly increasing order, the last element is always a peak element. For example, 50 is peak element in {10, 20, 30, 40, 50}.
2) If input array is sorted in strictly decreasing order, the first element is always a peak element. 100 is the peak element in {100, 80, 60, 50, 20}.
3) If all elements of input array are same, every element is a peak element.

It is clear from above examples that there is always a peak element in input array in any input array.

A simple solution is to do a linear scan of array and as soon as we find a peak element, we return it. The worst case time complexity of this method would be O(n).

Can we find a peak element in worst time complexity better than O(n)?
We can use Divide and Conquer to find a peak in O(Logn) time. The idea is Binary Search based, we compare middle element with its neighbors. If middle element is not smaller than any of its neighbors, then we return it. If the middle element is smaller than the its left neighbor, then there is always a peak in left half (Why? take few examples). If the middle element is smaller than the its right neighbor, then there is always a peak in right half (due to same reason as left half). Following are C and Java implementations of this approach.

## C/C++

 `// A C++ program to find a peak element element using divide and conquer ` `#include ` ` `  `// A binary search based function that returns index of a peak element ` `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); ` `} ` ` `  `/* Driver program to check above functions */` `int` `main() ` `{ ` `    ``int` `arr[] = {1, 3, 20, 4, 1, 0}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``printf``(``"Index of a peak point is %d"``, findPeak(arr, n)); ` `    ``return` `0; ` `} `

## Java

 `// A Java program to find a peak element element using divide and conquer ` `import` `java.util.*; ` `import` `java.lang.*; ` `import` `java.io.*; ` ` `  `class` `PeakElement ` `{ ` `    ``// A binary search based function that returns index of a peak ` `    ``// element ` `    ``static` `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 neighbor 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 neighbor ` `        ``// 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() ` `    ``static` `int` `findPeak(``int` `arr[], ``int` `n) ` `    ``{ ` `        ``return` `findPeakUtil(arr, ``0``, n-``1``, n); ` `    ``} ` ` `  `    ``// Driver method ` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` `        ``int` `arr[] = {``1``, ``3``, ``20``, ``4``, ``1``, ``0``}; ` `        ``int` `n = arr.length; ` `        ``System.out.println(``"Index of a peak point is "` `+ ` `                            ``findPeak(arr, n)); ` `    ``} ` `} `

## Python3

 `# A python 3 program to find a peak  ` `# element element using divide and conquer ` ` `  `# A binary search based function  ` `# that returns index of a peak element ` `def` `findPeakUtil(arr, low, high, n): ` `     `  `     ``# Find index of middle element ` `     ``# (low + high)/2  ` `     ``mid ``=` `low ``+` `(high ``-` `low)``/``2`  `     ``mid ``=` `int``(mid) ` `     `  `    ``# Compare middle element with its  ` `    ``# neighbours (if neighbours exist) ` `    ``if` `((mid ``=``=` `0` `or` `arr[mid ``-` `1``] <``=` `arr[mid]) ``and`  `       ``(mid ``=``=` `n ``-` `1` `or` `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 ` `    ``elif` `(mid > ``0` `and` `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() ` `def` `findPeak(arr, n): ` ` `  `    ``return` `findPeakUtil(arr, ``0``, n ``-` `1``, n) ` ` `  ` `  `# Driver code ` `arr ``=` `[``1``, ``3``, ``20``, ``4``, ``1``, ``0``] ` `n ``=` `len``(arr) ` `print``(``"Index of a peak point is"``, findPeak(arr, n)) ` `     `  `# This code is contributed by  ` `# Smitha Dinesh Semwal `

## C#

 `// A C# program to find  ` `// a peak element element  ` `// using divide and conquer ` `using` `System; ` ` `  `class` `GFG ` `{ ` `     `  `    ``// A binary search based  ` `    ``// function that returns  ` `    ``// index of a peak element ` `    ``static` `int` `findPeakUtil(``int` `[]arr, ``int` `low, ` `                            ``int` `high, ``int` `n) ` `    ``{ ` `        ``// Find index of  ` `        ``// middle element ` `        ``int` `mid = low + (high - low) / 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 neighbor ` `        ``// 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 neighbor ` `        ``// 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() ` `    ``static` `int` `findPeak(``int` `[]arr,  ` `                        ``int` `n) ` `    ``{ ` `        ``return` `findPeakUtil(arr, 0,  ` `                            ``n - 1, n); ` `    ``} ` ` `  `    ``// Driver Code ` `    ``static` `public` `void` `Main () ` `    ``{ ` `        ``int` `[]arr = {1, 3, 20, ` `                     ``4, 1, 0}; ` `        ``int` `n = arr.Length; ` `        ``Console.WriteLine(``"Index of a peak "` `+ ` `                                 ``"point is "` `+ ` `                            ``findPeak(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by ajit `

## PHP

 ` 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() ` `function` `findPeak(``\$arr``, ``\$n``) ` `{ ` `    ``return` `floor``(findPeakUtil(``\$arr``, 0,  ` `                              ``\$n` `- 1, ``\$n``)); ` `} ` ` `  `// Driver Code ` `\$arr` `= ``array``(1, 3, 20, 4, 1, 0); ` `\$n` `= sizeof(``\$arr``); ` `echo` `"Index of a peak point is "``,  ` `              ``findPeak(``\$arr``, ``\$n``); ` ` `  `// This code is contributed by ajit ` `?> `

Output :

`Index of a peak point is 2`

Time Complexity: O(Logn) where n is number of elements in input array.

Exercise:
Consider the following modified definition of peak element. An array element is peak if it is greater than its neighbors. Note that an array may not contain a peak element with this modified definition.

Related Problem:
Find local minima in an array