http://www.lintcode.com/en/problem/find-peak-element/#

this problem is aimed to find one of the many peak element

the condition that it starts with going up and ends with going down tells us that there is at least one peak.

so if the cur position is in a upwards slope, it means that the possible peak should be on the right side of it so we keep the right half, if the cur position is a downwards slope, it means that possible peak should be on the left side of it so we keep the left half

--note that if there are duplicates, then we can't define which one is peak if it falls on the flat part

class Solution {
    /**
     * @param A: An integers array.
     * @return: return any of peek positions.
     */
    public int findPeak(int[] A) {
        // write your code here
        if (A == null) {
            return -1;
        }

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

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (A[mid] > A[mid - 1] && A[mid] > A[mid + 1]) {
                return mid;
            } else if (A[mid] > A[mid - 1] && A[mid] < A[mid + 1]) {
                start = mid;
            } else {
                end = mid;
            } 
        }

        if (A[start] > A[start - 1] && A[start] > A[start + 1]) {
            return start;
        }

        return end;


    }
}