class Solution {
public:
    /**
     * @param nums a mountain sequence which increase firstly and then decrease
     * @return then mountain top
     */
    int mountainSequence(vector<int>& nums) {
        // Write your code here
        int size = nums.size();
        if (size < 3) {
            return nums[0];
        }

        int start = 0;
        int end = size - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            int val_mid = nums[mid];
            int val_left = nums[mid - 1];
            int val_right = nums[mid + 1];
            //看nums[mid]左右两边，如果nums[mid]比左右两边大，说明是峰值
            //如果nums[mid]比左边大，比右边小，说明在递增区间。
            if (val_mid >= val_left && val_mid >= val_right) {
                return val_mid;
            } else if (val_mid >= val_left && val_mid <= val_right ) {
                start = mid;
            } else if (val_mid <= val_left && val_mid >= val_right) {
                end = mid;
            }
        }
        if (nums[start] > nums[end]) {
            return nums[start];
        } else {
            return nums[end];
        }
    }
};