Description
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的一个旋转，该数组的最小值为 1。NOTE：给出的所有元素都大于 0，若数组大小为 0，请返回 0。
Solutions
首先我们要理解一下题意，思路用二分查找。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if not rotateArray:
return
if len(rotateArray)==0:
return 0
index1=0
index2=len(rotateArray)-1
indexMid=index1
while (rotateArray[index1]>=rotateArray[index2]):
if (index2-index1)==1:
indexMid=index2
break
indexMid = (index1+index2)//2
# 如果index1 index2 indexMid三者相等
if rotateArray[index1]==rotateArray[index2] and rotateArray[indexMid]==rotateArray[index1]:
return self.minValue(rotateArray,index1,index2)
if rotateArray[indexMid]>=rotateArray[index1]:
index1=indexMid
if rotateArray[indexMid]<=rotateArray[index2]:
index2=indexMid
return rotateArray[indexMid]
def minValue(self,rotateArray,index1,index2):
res=rotateArray[index1]
for i in range(index1+1,index2+1):
if res>rotateArray[i]:
res=rotateArray[i]
return res
# 运行时间：969ms
# 占用内存：5752k