lintcode-binarysearch-maximum-number-in-mountain-sequence

https://www.lintcode.com/problem/maximum-number-in-mountain-sequence/description
//VERSION1 二分法 【思路】符合寻找第一个(最后一个)符合条件的情况---二分法
//没法直接二分，因为数组不是一个顺序排列的，所以，找出这个数组中的变化：升序数组中a[i]<a[i+1], 降序数组中a[i]>a[i+1]，二分找到这个变化
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
        if(nums.empty())
            return -1;
            
        int left = 0, right = nums.size() - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            
            if (nums[mid] > nums[mid+1]) { //此时降序数组
                right = mid;//右侧上山
            } else {//升序数组
                left = mid; //左侧上山
            }
        }
        return nums[left] > nums[right] ? nums[left] : nums[right]; //取两者最大的
    }
};



//一个比较啰嗦的版本，本质也是2分法，每次取两个点 ---- 每次比较的是中点的数
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
        if(nums.empty())
            return -1;

        int left = 0, right = nums.size() - 1;
        while (left + 1 < right) {
            int m1 = left + (right - left) / 2;//中点1 //偏向start
            int m2 = right - (right - m1) / 2;//中点2为right到m1的中点， 偏向right,这样写防止m1 m2重合
            if (nums[m1] < nums[m2]) {
                left = m1 + 1;//m2大---右移，所以left往右靠 //必须+1 //防止m1，m2重合
            } else if (nums[m1] > nums[m2]) {
                right = m2 - 1;//m1大---左移 所以right往左靠 //必须-1
                
            } else {
                left = m1;
                right = m2;
            }
        }
        return nums[left] > nums[right] ? nums[left] : nums[right]; //取两者最大的
    }
};