153. 寻找旋转排序数组中的最小值

https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/

解法一：直接一次遍历

class Solution:
    def findMin(self, nums: List[int]) -> int:
        res = nums[0]
        for i in range(1, len(nums)):
            res = min(res, nums[i])
        return res

解法二：二分

参考33. 搜索旋转排序数组

以下算法只对严格旋转（必须有断点，两段都升序，无重复，长度>2）序列有效，但对升序需要特殊处理（bug：对严格升序的序列，算法结果low=n-1）。 思路也很简单，即不断往断点处靠拢：

1.初始left=0，right=n-1

2.当left<=right时，每次计算中点，若nums[mid]在左分支，low=mid+1；否则high=mid-1

3.循环结束时，左断点为right，右断点为left

本题求最小值，因此返回右断点。求最大值则返回左断点。

class Solution:
    def findMin(self, nums) -> int:
        n = len(nums)
        left, right = 0, n - 1
        if nums[n - 1] > nums[0]:  # 若是升序
            return nums[0]
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] >= nums[0]:  # 在左分支
                left = mid + 1
            else:  # 在右分支
                right = mid - 1
        # 结束时左断点为right，右断点为left
        # 例外情况：若是升序，left会越界
        if left > n - 1:
           return nums[0]
        else:  # 否则等于右断点
            return nums[left]