2.6 Find Peak Element

Find peak element in array, assume:

1. All adjacent number in array is different
2. A[0] < A[1] && A[A.length - 2] > A[A.length - 1]

Example

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

Return index 1 (which is number 2) or 6 (which is number 7)

Logical Steps

1. If mid->mid+1 is increasing, move search to right (start = mid)
2. If mid->mid+1 is decreasing, move search to left (end = mid)
3. If start and end are on different peaks, move to left (end=mid) to return first peak

Code Template

public int findPeak(int[] A) {
    if (A==null || A.length<3)
        return -1;

    int start = 1;
    int end = A.length-2;

    while(start + 1 < end) {
        int mid = (start+end)/2;
        // if m->m+1 increasing, move search to right
        if (A[mid] < A[mid+1]){
            start = mid;
        // if m->m+1 decreasing, move search to left
        }else if (A[mid] > A[mid+1]){
            end = mid;
        // if start and end are both on peak but different element
        // move search to left to return first peak in array
        }else{
            end = mid;
        }
    }

    // return the larger between start and end as peak
    if (A[start] > A[end]){
        return start;
    }else{
        return end;
    }
}

Common Mistakes

1. Consider m-1,m,m+1 pattern, and forgot the "valley"

    /** this is a mistake example
    * not only peak will be returned, valley will also 
    * be returned
    */
    while(start + 1 < end) {
        int mid = (start+end)/2;
   
        if (A[mid-1] < A[mid] && A[mid+1] > A[mid]){
            start = mid;
        }else if (A[mid-1] > A[mid] && A[mid+1]<A[mid]){
            end = mid;
        }else{
            // peak and valley will both be returned
            // no neat way to distinguish peak and vallay
            return mid;
        }
    }