直接找最小值

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        return min(rotateArray)

虽然很想就这样过这道题,但是这种做法没有意义
显然,这是一个局部排好序的列表
显然,二分查找上场了

二分查找

思路

保证rotateArray[left]为全场最小,当rotateArray[left]<rotateArray[right]时,证明进入了有序数组,直接输出

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray)==0:
            return 0
        left=0
        right=len(rotateArray)-1
        while left<right:
            if rotateArray[left]<rotateArray[right]:
                return rotateArray[left]
            mid=left+(right-left)//2
            #左边有序取另一半
            if rotateArray[left]<rotateArray[mid]:
                left=mid+1
            #右边有序右边取最小
            elif rotateArray[mid]<rotateArray[right]:
                right=mid
            #前面两个相等的时候,left进一继续
            else :
                left+=1
        return rotateArray[left]