Maximum Number in Mountain Sequence

Given a mountain sequence ofnintegers which increase firstly and then decrease, find the mountain top.

Example

Givennums=[1, 2, 4, 8, 6, 3]return8
Givennums=[10, 9, 8, 7], return10

Solution:

Typical binary search problem. If mid is on the left half, eliminate all elements to the left, and vice versa.

Note: we have to inspect the previous element to determine which side the mid point is on, we can not use nums[left] / nums[right] because duplicates might occur on both sides.

 public int mountainSequence(int[] nums) {
    int left  = 0,
        right = nums.length - 1;
    while (left + 1 < right) {
        int mid = left + (right - left) / 2;
        if (mid == 0 || nums[mid] > nums[mid - 1]) {
            left = mid;
        } else {
            right = mid;
        }
    }
    return Math.max(nums[left], nums[right]);
}