直接找最小值
# -*- 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]