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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param rotateArray int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        # return min(rotateArray) 直接调用函数
        # 二分查找时间复杂度为O(logn)
        left = 0
        right = len(rotateArray) - 1
        if rotateArray[left] < rotateArray[right]: # 如果是排好序的数组，直接返回第一个值
            return rotateArray[left]
        while left < right:
            if right - left == 1:
                break
            mid = (left + right) // 2
            if rotateArray[left] == rotateArray[right] and rotateArray[left] == rotateArray[mid]:
                # 对应[1,0,1,1,1]和[1,1,1,0,1]无法判定中间元素是属于前数组还是后数组的时候，顺序查找
                return self.minInorder(rotateArray, left, right)
            if rotateArray[mid] >= rotateArray[left]: # 注意等于号，中间值在前递增数组，最小值在后半段
                left = mid
            elif rotateArray[mid] <= rotateArray[right]: # 注意等于号，中间值在后递增数组，最小值在前半段
                right = mid
        return rotateArray[right]
    def minInorder(self, array, left, right):
        result = array[left]
        for i in range(len(array)):
            if result > array[i]:
                result = array[i]
        return result