75.Find Peak Element

1.Description(Medium)

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.

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)

2.Code

以下只适用于lintcode,因为Lintcode的题目限制了A[0] < A[1] && A[A.length - 2] > A[A.length - 1].，所以可以start=1;end=length-2;

但是leetcode没有限制，所以词方法不行。

public int findPeak(int[] A){
        if(A==null || A.length==0){
            return -1;
        }
        //caution: start and end;
        int start=1;
        int end=A.length-2;
        while(start+1<end){
            int mid=start+(end-start)/2;
            //top directly return 
            if(position(A,mid)==2){
                return mid;
            }
            //increase 
            else if(position(A,mid)==1){
                start=mid;
            }
            //decrease
            else if(position(A,mid)==-1){
                end=mid;
            }
            //bottom
            else if(position(A,mid)==-2){
                start=mid;  //or end =mid;
            }
        }
        if(position(A,start)==2){
            return start;
        }
        if(position(A,end)==2){
            return end;
        }
        return -1;
    }


    public int position(int[] A,int mid){
        int middle=A[mid];
        int pre=A[mid-1];
        int post=A[mid+1];
        //bottom
        if(middle<pre && middle<post){
            return -2;
        }  
        //decrease
        else if(middle<pre && middle>post){
            return -1;
        }
        //top
        else if(middle>pre && middle>post){
            return 2;
        }
        //increase
        else if(middle>pre && middle<post){
            return 1;
        }
        return 0;
    }