1.17 剑指offer 旋转数组的最小数字

题目

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

思路

旋转数组，分为两部分有序数组，可以采用二分查找方法。
两个指针p1和p2，分别初始为数组首和尾。
如果mid（p1和p2中间）小于p1指向的值，那么mid属于后部分的有序数组，移动p2到mid
如果mid大于或等于p1指向的值，那么mid属于前部分的有序数组，移动p1到mid
循环直到p1和p2相邻，p2指向的值为最小值。

代码

def minNumberInRotateArray(rotateArray):
    if len(rotateArray) == 0:
        return 0
    
    p1 = 0
    p2 = len(rotateArray)-1
    while p2-p1 != 1:
        mid = int((p1+p2)/2)
        if rotateArray[p1] == rotateArray[p2] and rotateArray[p1] == rotateArray[mid]:
            return findMin(rotateArray)
        if rotateArray[mid]>=rotateArray[p1]:
            p1 = mid
        else:
            p2 = mid
    return rotateArray[p2]

def findMin(l):
    m = l[0]
    for i in l:
        if i < m:
            m = i
    return m

注意问题

大于等于，都移动p1
如果p1和p2和mid值都一样，那么无法判断移动哪个，只能遍历数组了。