585. Maximum Number in Mountain Sequence

Maximum Number in Mountain Sequence
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

思路： 就是两边往中间走，最后判断start和end即可，按照九章的模板写万无一失。

class Solution:
    """
    @param nums: a mountain sequence which increase firstly and then decrease
    @return: then mountain top
    """
    def mountainSequence(self, nums):
        if nums == None or len(nums) == 0:
            return -1

        start, end = 0, len(nums)-1
        while start + 1 < end:
            mid = start + (end - start) // 2
            # sqrt = mid ** 2
            # sqrtPlus = (mid + 1) ** 2
            if nums[mid] < nums[mid+1]:
                start = mid
            # elif sqrt < x:
                # start = mid
            else:
                end = mid

        if nums[start] > nums[end]:
            return nums[start]
        else:
            return nums[end]

如果需要优化O(n)的时间复杂度，一般只能是O(logn)的二分法

binary search可以有多种写法，如果每次都写的不一样，就会造成对于结束条件，指针变化的混乱，所以我们要找到一种固定的模板，通过修改模板来解决题目。这里我选择了九章算法提供的模板。
四点要素:
start + 1 < end 这样就不用考虑两个指针的前后，最后结束时一定是相邻的
start + (end - start) / 2 虽然对python来说不重要，但是对于Java等可以防止溢出
A[mid] ==, <, > 这个会根据题目的不同来调整
A[start] A[end] ? target