Find Peak Element

Leave a comment

October 1, 2016 by oneOokay

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.

二分法:不要忽略题目的条件,起点1,2个元素是递增的,终点最后两个元素是递减的。九章:

public int findPeak(int[] A) {
        int start = 1, end = A.length-2; // 1.答案在之间,2.不会出界 
        while(start + 1 <  end) {
            int mid = (start + end) / 2;
            if(A[mid] < A[mid - 1]) { //mid-1到mid递减,说明左边有一个peak
                end = mid;
            } else if(A[mid] < A[mid + 1]) { //mid-1, mid到mid+1递增,而且终点是递减的,说明中间一定有一个peek
                start = mid;
            } else { //此时mid为一个凹点,所以左右必然各存在一个peek,所以这里end=mid或者start=mid都可以。
                end = mid;
            }
        }
        if(A[start] < A[end]) {
            return end;
        } else { 
            return start;
        }
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: