leetcode154. Find Minimum in Rot

原题链接https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1
Example 2:

Input: [2,2,2,0,1]
Output: 0

本题主要是会出现一些特殊情况，比如
1.[1,2,3,4,5]未发生翻转的情况
2.[1,1,1,1,1,1]数字全部一样
3.[1,1,1,1,0,1,1,1]数字大部分相等

本题思路是，通过对首尾元素的比较结果进行分类。
若arr[low] == arr[high]，则此时大概率是二分法下最坏情况，此时二分法的时间复杂度为O(N),所以直接采用顺序比较。（偷个小懒，更优解法二刷再说）
若arr[low] < arr[high],则最小元素为首位元素。
若arr[low] >arr[high],则采用二分法。

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:return 0
        if n == 1:return nums[0]

        def get_min(arr,low,high):
            mid = low + ((high - low) >> 1)
            if arr[mid] > arr[mid + 1]:
                return arr[mid + 1]
            elif arr[mid] < arr[mid - 1]:
                return arr[mid]
            elif arr[high] > arr[mid] or arr[low] > arr[mid]:
                return get_min(arr,low, mid-1)
            elif arr[low] < arr[mid] or arr[high] < arr[mid]:
                return get_min(arr,mid+1, high)
            
        if nums[0] < nums[n-1]:
            return nums[0]
        elif nums[0] > nums[n-1]:
            return get_min(nums, 0, n-1)
        else:
            mins = float('inf')
            for num in nums:
                if num < mins:
                    mins = num
            return mins