# Find Peak Element

## Question

There is an integer array which has the following features:

* The numbers in adjacent positions are different.
* A[0] < A[1] && A[A.length - 2] > A[A.length - 1].

We define a position P is a peek if A[P] > A[P-1] && A[P] > A[P+1].

Find a peak element in this array. Return the index of the peak.

Note
The array may contains multiple peeks, find any of them.

Example
[1, 2, 1, 3, 4, 5, 7, 6]

return index 1 (which is number 2)  or 6 (which is number 7)

Challenge
Time complexity O(logN)


## 題解1 - lintcode

### 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 l = 0, r = A.length - 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;
}
}


## 題解2 - leetcode

leetcode 上的題和 lintcode 上有細微的變化，題目如下：

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.


### C++

class Solution {
public:
int findPeakElement(vector<int>& arr) {
int N = arr.size();
int lo = 0, hi = N;
while(lo < hi) {
int mi = lo + (hi - lo)/2;
if( (mi == 0 || arr[mi-1] <= arr[mi] ) && (mi == N-1 || arr[mi] >= arr[mi+1]) )
return mi;
else if((mi == 0 || arr[mi-1] <= arr[mi] ))
lo = mi + 1;
else
hi = mi;
}
return -1;
}
};


### Java

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

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

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


### 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，弄混的話會編譯錯誤。