Find Peak Element

Find Peak Element

44%

Accepted

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)

class Solution {

    /**

     * @param A: An integers array.

     * @return: return any of peek positions.

     */

    public int findPeak(int[] A) {

        // write your code here

        

        int l = 0, r = A.length-1;

        

        while(l <= r){

            if(l == r) return l;

            int mid = (l+r)/2;

            if(A[mid] > A[mid+1]){

                r = mid;

            } else l = mid+1;

        }

        return l;

    }

}

class Solution {

    /**

     * @param A: An integers array.

     * @return: return any of peek positions.

     */

    public int findPeak(int[] A) {

        // write your code here

        

        for(int i = 1; i < A.length; i++){

            if(A[i] < A[i-1]){

                return i-1;

            }

        }

        return A.length+1;

    }

}