Maximum Number in Mountain Sequence

• Lintcode : 585 / Leetcode :
• Level : Medium

Problem

Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.

Example
Example 1:

Input: nums = [1, 2, 4, 8, 6, 3] 
Output: 8
Example 2:

Input: nums = [10, 9, 8, 7], 
Output: 10
Notice
Arrays are strictly incremented, strictly decreasing

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(logn)
space: O(1)

Answer

class Solution {
public:
    int mountainSequence(vector<int> &nums) {
        // corner case : if nums.size() == 0
        int l = 0, r = nums.size() - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] > nums[mid + 1]) {
                r = mid;
            }else {
                l = mid;
            }
        }
        if (nums[l] > nums[r]) return nums[l];
        return nums[r];
    }
};

tags: Binary Search

​