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

NC71 旋转数组的最小数字

描述 有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000 要求：空间复杂度：O(1) ，时间复杂度：O(logn)

和题目“NC48 在旋转过的有序数组中寻找目标值”有点像，就是这个数组是不降序的，需要再处理一下。思路是一样的

思路：数组分成两部分，左边和右边，左右内部升序，左边值不小于右边，由此二分确定分割点，最小值为分割点的值。由于考虑到类似[5,5,5,5,3,5,5,5]或[5,5,5,5,9,5,5,5]或[5,5,5,5,5,5,5,5]这种情况，所以我先用while循环确保rotateArray[left]和rotateArray[right]不相等，确定left和right。这样处理后，rotateArray[left] 一定大于 rotateArray[right]，左边的值一定大于右边的值。 之后用二分。

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param rotateArray int整型一维数组 
# @return int整型
#
class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        if len(rotateArray) == 1:
            return rotateArray[0]
        left = 0
        right = len(rotateArray) - 1
        while (rotateArray[left] == rotateArray[right]) & (left < right):
            left += 1
        if rotateArray[left] <= rotateArray[right]:
            return rotateArray[left]
        k = (left + right) >> 1
        while left < right:
            print(rotateArray[k],rotateArray[left],rotateArray[right])
            if rotateArray[k] >= rotateArray[left]:
                if rotateArray[k + 1] < rotateArray[left]:
                    return rotateArray[k + 1]
                left = k + 1
            else:
                if rotateArray[k - 1] >= rotateArray[left]:
                    return rotateArray[k]
                right = k - 1
            k = (left + right) >> 1