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

class Solution:
    def minNumberInRotateArray(self , rotateArray: List[int]) -> int:
        # write code here
        if len(rotateArray) == 1:
            return rotateArray[0]
        left, right = 0, len(rotateArray)-1
        while left < right:
            mid = (left + right) // 2
            if rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            elif rotateArray[mid] < rotateArray[right]:
                right = mid
            else:
                right = right - 1
        return rotateArray[left]
		
		
解题思路：
	python中有min函数和列表排序方法可求得最小值，但是这两种方法的时间复杂度为O(n)，舍弃不用。
	
	该题用二分法来解决较为合适：
		1、特殊情况：列表长度为1，则最小值为列表中仅存在的那个值；
		2、因为列表为非降序列表且旋转，所以若中间值大于最末尾的值，则最小值在右半区间；反之若中间值小于最末尾的值，则最小值在左半区间；若中间值等于最末尾的值，表示该列表中存在重复值，我们只需将最左边的索引往前移动一个重新检查即可。