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.

Have you met this question in a real interview?

Yes

Example

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

Return index1(which is number 2) or6(which is number 7)

Challenge

Time complexity O(logN)

class Solution {

public:

/\*\*

 \* @param A: An integers array.

 \* @return: return any of peek positions.

 \*/

int findPeak\(vector<int> A\) {

    // write your code here

    if \(A.size\(\) < 3\) {

        return -1;

    }

    int start = 0, end = A.size\(\) - 1;



    while \(start + 1 < end\) {

        int mid = \(end - start\) / 2 + start;

        // cout << start << endl;

        // cout << end << endl;

        // cout << mid << endl;

        if \(A\[mid\] > A\[mid - 1\] && A\[mid\] > A\[mid + 1\]\) {

            return mid;

        }

        if \(A\[mid\] < A\[mid + 1\]\) {

            start = mid;

        } else {

            end = mid;

        }

    }



    return -1;

}

};