11旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

有序和部分有序的，都可以使用二分法做。注意头、中、尾的数字相同这种特殊情况。

def min(rotateArray):
    if len(rotateArray) == 0:
        return

    left = 0
    right = len(rotateArray) - 1
    middle = 0

    while rotateArray[left] >= rotateArray[right]:
        if right - left == 1:
            return rotateArray[right]

        middle = (left + right) // 2
        
        if rotateArray[left] == rotateArray[right] and\
                rotateArray[middle] == rotateArray[right]:
            min_item = rotateArray[left]
            for item in rotateArray[left:right]:
                if item < min_item:
                    min_item = item
            return min_item

        if rotateArray[middle] >= rotateArray[left]:
            left = middle
        else:
            right = middle

if __name__ == "__main__":
    lyst15 = [3, 4, 5, 1, 2]
    lyst0 = [3, 3, 3, 1, 2]
    lyst12 = [2, 1, 2, 2, 2]
    assert min(lyst15) == 1
    assert min(lyst0) == 1
    assert min(lyst12) == 1