Given a mountain sequence of n integers which increase firstly and then decrease, find the mountain top.+
Example
Given nums = [1, 2, 4, 8, 6, 3] return 8
Given nums = [10, 9, 8, 7], return 10
Solution
class Solution:
# @param {int[]} nums a mountain sequence which increase firstly and then decrease
# @return {int} then mountain top
def mountainSequence(self, nums):
# Write your code here
left, right = 0, len(nums) - 1
while left + 1 < right:
m1 = left + (right - left) / 2
m2 = right - (right - m1) / 2
if nums[m1] < nums[m2]:
left = m1 + 1
elif nums[m1] > nums[m2]:
right = m2 - 1
else:
left = m1
right = m2
return max(nums[left], nums[right])