# Find Peak Element

## Question

### Problem Statement

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.

#### Note:

Your solution should be in logarithmic complexity.

#### Credits:

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

## 题解1

### Python

class Solution:
#@param A: An integers list.
#@return: return any of peek positions.
def findPeak(self, A):
if not A:
return -1

l, r = 0, len(A) - 1
while l + 1 < r:
mid = l + (r - l) / 2
if A[mid] < A[mid - 1]:
r = mid
elif A[mid] < A[mid + 1]:
l = mid
else:
return mid
mid = l if A[l] > A[r] else r
return mid


### C++

class Solution {
public:
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
int findPeak(vector<int> A) {
if (A.size() == 0) return -1;

int l = 0, r = A.size() - 1;
while (l + 1 < r) {
int mid = l + (r - l) / 2;
if (A[mid] < A[mid - 1]) {
r = mid;
} else if (A[mid] < A[mid + 1]) {
l = mid;
} else {
return mid;
}
}

int mid = A[l] > A[r] ? l : r;
return mid;
}
};


### Java

class Solution {
/**
* @param A: An integers array.
* @return: return any of peek positions.
*/
public int findPeak(int[] A) {
if (A == null || A.length == 0) return -1;

int lb = 0, ub = A.length - 1;
while (lb + 1 < ub) {
int mid = lb + (ub - lb) / 2;
if (A[mid] < A[mid + 1]) {
lb = mid;
} else if (A[mid] < A[mid - 1]){
ub = mid;
} else {
// find a peak
return mid;
}
}

// return a larger number
return A[lb] > A[ub] ? lb : ub;
}
}


### 复杂度分析

#### Java - compact implementationleetcode_discussion

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

int start = 0, end = nums.length - 1, mid = end / 2;
while (start < end) {
if (nums[mid] < nums[mid + 1]) {
// 1 peak at least in the right side
start = mid + 1;
} else {
// 1 peak at least in the left side
end = mid;
}
mid = start + (end - start) / 2;
}

return start;
}
}


C++ 的代码可参考 Java 或者 @xuewei4d 的实现。

Warning leetcode 和 lintcode 上给的方法名不一样，leetcode 上的为findPeakElement而 lintcode 上为findPeak，弄混的话会编译错误。