Lintcode: 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 

Binary Search

Solution 1:
Iterate each element
Time: O(n)
Space: O(1)

Solution 2:
Binary search:
http://siddontang.gitbooks.io/leetcode-solution/content/array/find_peak_element.html
From the problem, we can see that there are at least three elements in the array.
Compare middle with its adjacent two elements left and right.

If middle > left && middle > right return middle
else if middle < left, end = middle - 1. (there must be a peak from beginning to middle - 1. )
else if middle < right, start = middle + 1. (there must be at least a peak from middle + 1 to end)

Time: O(logn)
Space: O(1)

class Solution {
public:
    /**
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    int findPeak(vector<int> A) {
        // write your code here
        int start = 1;
        int end = A.size() - 2;
        while(start <= end){
            int mid = (start + end) / 2;
            if(A[mid - 1] < A[mid] && A[mid] > A[mid + 1]) return mid;
            if(A[mid - 1] > A[mid]) end = mid - 1;
            else if(A[mid] < A[mid + 1]) start = mid + 1;
        }
    }
};