题解 | #旋转数组的最小数字#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberInRotateArray(self , nums: List[int]) -> int:
        #该题比较中间值与最右边的值的大小，如果中间值大于最右边，那说明列表已经发生了旋转，最小值肯定在右边，如果中间值小于最右边，那说明列表没有发生反转，最小值还是在左边，
        # write code here
        left,right=0,len(nums)-1
        
        # 列表的(左+右)//2就是中间的数值。
        while left <right:
            mid=(left+right)//2  # 偶数个比较靠左
            if nums[mid] < nums[right]:
                right=mid
            elif nums[mid]>nums[right]:
                left=mid+1
            else:
                right=right-1

        return nums[right]
        

该题的核心在于：right就是最小值的下标。

如果mid<right,说明还是非降序，证明列表还没有被旋转，那么最小值肯定在左边，如果mid二分到最后一个数，那么mid就是最小值，所以right=mid；

如果mid>right,那就说明这一部分是原列表的尾部和旋转之后的部分连在一起了，那么最小值一定在右边；

如果mid=right，就将right-1，因为right-1，肯定是等于mid，或者是等于于mid相同的值的元素，这样不会丢掉数据。