# Find Peak Element

Leave a commentOctober 1, 2016 by oneOokay

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.

##### Notice：The array may contains multiple peeks, find any of them.

二分法：不要忽略题目的条件，起点1，2个元素是递增的，终点最后两个元素是递减的。九章：

public int findPeak(int[] A) { int start = 1, end = A.length-2; // 1.答案在之间，2.不会出界 while(start + 1 < end) { int mid = (start + end) / 2; if(A[mid] < A[mid - 1]) { //mid-1到mid递减，说明左边有一个peak end = mid; } else if(A[mid] < A[mid + 1]) { //mid-1, mid到mid+1递增，而且终点是递减的，说明中间一定有一个peek start = mid; } else { //此时mid为一个凹点，所以左右必然各存在一个peek，所以这里end=mid或者start=mid都可以。 end = mid; } } if(A[start] < A[end]) { return end; } else { return start; } }

Advertisements