# [LeetCode 162] Find Peak Element

### Question

link

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] = -8`.

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.

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

### Analysis

This basically is a binary search question. Instead of checking the values, we check the slope (upgoing or downslope).

The important point is the special cases like [1, 2, 3] or [3, 2, 1], we need to return the corner values. Well there’re 2 ways to handle these corner cases.

### Solution

First, referring to G4G, the corner case is handled in this way:

``````if ((mid == 0 || arr[mid-1] <= arr[mid]) &&
(mid == n-1 || arr[mid+1] <= arr[mid]))
return mid;
``````

The code 1 below is doing similar things. That code is readable and easy to come up with. I recommend this solution during a interview.

For those who are interested, there is a extremely concise solution thanks to Duplan. I have the Java version posted below as code 2.

### Code

Code 1

``````public class Solution {
public int findPeakElement(int[] num) {
if (num == null || num.length == 0) {
return 0;
} else if (num.length == 1) {
return 0;
} else if (num[0] > num[1]) {
return 0;
} else if (num[num.length - 2] < num[num.length - 1]) {
return num.length - 1;
}
// now the leftmost edge is increasing
// and the rightmost edge is also increasing backwards
return helper(num, 0, num.length - 1);
}

public int helper(int[] num, int left, int right) {
int mid = left + (right - left) / 2;
if (left + 2 == right) {
return mid;
} else if (num[mid] > num[mid + 1]) {
// middle is decreasing, so peak on the left side
return helper(num, left, mid + 1);
} else {
return helper(num, mid, right);
}
}
}
``````

Code 2

``````public class Solution {
public int findPeakElement(int[] num) {
if (num == null || num.length == 0) {
return 0;
}
return helper(num, 0, num.length - 1);
}

public int helper(int[] num, int left, int right) {
int mid = left + (right - left) / 2;
if (left == right) {
return left;
} else if (num[mid] > num[mid + 1]) {
// middle is decreasing, so peak on the left side
return helper(num, left, mid);
} else {
return helper(num, mid + 1, right);
}
}
}
``````