面试题9：旋转数组最小数字

【题目描述】：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
【解法】：
自己思路是采用两个指针，一个从左往右，一个从右往左，直到找到那个最小元素为止。
1.从左往右找到最小值的条件是：
array[left]>array[left+1]
array[left+1]为最小值
2.从右往左找到最小值的条件是
array[right]<array[right-1]
array[right]为最小值
【代码】

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        n = len(rotateArray)
        if n==0:
            return 0
        left = 0
        right = n-1
        #两个指针判断，一个从左往右，一个从右往左，直到找到那个最小元素为止
        while left<right-1:
            if rotateArray[left]<=rotateArray[left+1]:
                left+=1
            #从左往右找到最小元素，最小元素在left+1位置
            else:
                break
            if rotateArray[right]>=rotateArray[right-1]:
                right-=1
            #从右往左找到最小元素，最小元素在right位置
            else:
                break
        return min(rotateArray[left+1],rotateArray[right])

【优化解法】二分查找
left指向递增序列的最后一个，right指向第二个递增序列的第一个
故array[right]处为最小值

class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        n = len(rotateArray)
        if n==0:
            return 0
        left = 0
        right = n-1
        #两个指针判断，一个从左往右，一个从右往左，直到找到那个最小元素为止
        while left<right-1:
            '''if rotateArray[left]<=rotateArray[left+1]:
                left+=1
            #从左往右找到最小元素，最小元素在left+1位置
            else:
                break
            if rotateArray[right]>=rotateArray[right-1]:
                right-=1
            #从右往左找到最小元素，最小元素在right位置
            else:
                break'''
            #二分查找
            mid = (left+right)/2
            if rotateArray[mid]>=rotateArray[left]:
                left = mid
            if rotateArray[mid]<=rotateArray[right]:
                right = mid  
        return rotateArray[right]