LintCode (75) find peak element

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.

Have you met this question in a real interview? 

Yes

Example

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

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

Note

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

Challenge

Time complexity O(logN)

Tags Expand  


算是divide and conquer的一种，画一下曲线就知道了，如果发现是递增，那么beg移到mid，如果发现递减，end移到mid...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

class Solution { public: /** * Because A[0]<A[1] and A[n-2]>A[n-1] * there must exist one solution * use mid to check if it is asscending or descending * if asscending to left, check right hand * else check left hand untill we run out of solutions * @param A: An integers array. * @return: return any of peek positions. */ int findPeak(vector<int> A) { // write your code here int n=A.size(); if (n==0) return -1; if (n==1) return 0; int beg=0; int end=n-1; while(beg+1<end){ int mid=beg+(end-beg)/2; if (A[mid]>A[mid-1] && A[mid]>A[mid+1]) return mid; else if (A[mid]<A[mid-1]) end=mid; else beg=mid; } return -1; } };