旋转数组的最小数字

题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
简单方法：

def minNumberInRotateArray(self, rotateArray):
    # write code here
    n = len(rotateArray)
    if n == 0:
        return None
    j = rotateArray[0]
    for i in range(1, n):
        if rotateArray[i] < j:
            return rotateArray[i]
        j = rotateArray[i]
    return rotateArray[0]

二分法：

 def minNumberInRotateArray(self, rotateArray):
    # write code here
    n = len(rotateArray) - 1
    if n == 0:
        return None
    left = 0
    right = n
    while(left < right):
        if rotateArray[left] < rotateArray[right]:
            return rotateArray[left]
        mid = int((left + right) / 2)
        if rotateArray[left] < rotateArray[mid]:
            left = mid + 1
        elif rotateArray[mid] < rotateArray[mid]:
            right = mid
        else:
            left += 1
    return rotateArray[left]

如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字
比如 array = [4,6]
array[low] = 4; array[mid] = 4; array[high] = 6;
如果high = mid - 1，就会产生错误，因此high = mid
但情形(1)中low = mid + 1就不会错误。