## 162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:

Your solution should be in logarithmic complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

b'
\n\n

## Solution

\n
\n

#### Approach #1 Linear Scan [Accepted]

\n

In this approach, we make use of the fact that two consecutive numbers and are never equal. Thus, we can traverse over the array starting from the beginning. Whenever, we find a number , we only need to check if it is larger than the next number for determining if is the peak element. The reasoning behind this can be understood by taking the following three cases which cover every case into which any problem can be divided.

\n

Case 1: All the numbers appear in a descending order. In this case, the first element corresponds to the peak element. We start off by checking if the current element is larger than the next one. The first element satisfies this criteria, and is hence identified as the peak correctly. In this case, we didn\'t reach a point where we needed to compare with also, to determine if it is the peak element or not.

\n

\n

Case 2: All the elements appear in ascending order. In this case, we keep on comparing with to determine if is the peak element or not. None of the elements satisfy this criteria, indicating that we are currently on a rising slope and not on a peak. Thus, at the end, we need to return the last element as the peak element, which turns out to be correct. In this case also, we need not compare with , since being on the rising slope is a sufficient condition to ensure that isn\'t the peak element.

\n

\n

Case 3: The peak appears somewhere in the middle. In this case, when we are traversing on the rising edge, as in Case 2, none of the elements will satisfy . We need not compare with on the rising slope as discussed above. When we finally reach the peak element, the condition is satisfied. We again, need not compare with . This is because, we could reach as the current element only when the check failed for the previous( element, indicating that . Thus, we are able to identify the peak element correctly in this case as well.

\n

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We traverse the array of size once only.

\n
• \n
• \n

Space complexity : . Constant extra space is used.

\n
• \n
\n
\n

#### Approach #2 Recursive Binary Search [Accepted]

\n

Algorithm

\n

We can view any given sequence in array as alternating ascending and descending sequences. By making use of this, and the fact that we can return any peak as the result, we can make use of Binary Search to find the required peak element.

\n

In case of simple Binary Search, we work on a sorted sequence of numbers and try to find out the required number by reducing the search space at every step. In this case, we use a modification of this simple Binary Search to our advantage. We start off by finding the middle element, from the given array. If this element happens to be lying in a descending sequence of numbers. or a local falling slope(found by comparing to its right neighbour), it means that the peak will always lie towards the left of this element. Thus, we reduce the search space to the left of (including itself) and perform the same process on left subarray.

\n

If the middle element, lies in an ascending sequence of numbers, or a rising slope(found by comparing to its right neighbour), it obviously implies that the peak lies towards the right of this element. Thus, we reduce the search space to the right of and perform the same process on the right subarray.

\n

In this way, we keep on reducing the search space till we eventually reach a state where only one element is remaining in the search space. This single element is the peak element.

\n

To see how it works, let\'s consider the three cases discussed above again.

\n

Case 1. In this case, we firstly find as the middle element. Since it lies on a falling slope, we reduce the search space to [1, 2, 3]. For this subarray, happens to be the middle element, which again lies on a falling slope, reducing the search space to [1, 2]. Now, acts as the middle element and it lies on a falling slope, reducing the search space to [1] only. Thus, is returned as the peak correctly.

\n

!?!../Documents/Find_Peak_Case1.json:1000,563!?!

\n

Case 2. In this case, we firstly find as the middle element. Since it lies on a rising slope, we reduce the search space to [4, 5]. Now, acts as the middle element for this subarray and it lies on a rising slope, reducing the search space to [5] only. Thus, is returned as the peak correctly.

\n

!?!../Documents/Find_Peak_Case2.json:1000,563!?!

\n

Case 3. In this case, the peak lies somewhere in the middle. The first middle element is . It lies on a rising slope, indicating that the peak lies towards its right. Thus, the search space is reduced to [5, 1]. Now, happens to be the on a falling slope(relative to its right neighbour), reducing the search space to [5] only. Thus, is identified as the peak element correctly.

\n

!?!../Documents/Find_Peak_Case3.json:1000,563!?!

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We reduce the search space in half at every step. Thus, the total search space will be consumed in steps. Here, refers to the size of array.

\n
• \n
• \n

Space complexity : . We reduce the search space in half at every step. Thus, the total search space will be consumed in steps. Thus, the depth of recursion tree will go upto .

\n
• \n
\n
\n

#### Approach #3 Iterative Binary Search [Accepted]

\n

Algorithm

\n

The binary search discussed in the previous approach used a recursive method. We can do the same process in an iterative fashion also. This is done in the current approach.

\n\n

Complexity Analysis

\n
\n
• \n

Time complexity : . We reduce the search space in half at every step. Thus, the total search space will be consumed in steps. Here, refers to the size of array.

\n
• \n
• \n

Space complexity : . Constant extra space is used.

\n
• \n
\n
\n

Analysis written by: @vinod23

\n
'