旋转数组的最小数字

旋转数组的最小数字

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

旋转数组的最小数字

分析

旋转数组有两个单调区间在每个单调区间内，都是递增的。右边的单调区间整体偏小。因此，若中间的数大于最右边的那个数。说明中间的那个数在左单调区间内。因此就可以确定最小值一定在中间的那个数的右边。其余同理。

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rArr):
        if not rArr:
            return 0
        low,hi = 0,len(rArr)-1
        while low<hi :
            mid = low + (hi-low)/2 #py3 must //
            if rArr[mid]<rArr[hi]:
                hi = mid
            elif rArr[mid]>rArr[hi]:
                low = mid +1
            else:
                hi-=1
        return rArr[low]
arr = list(map(int,raw_input().split())) #py3 input
so = Solution()
print so.minNumberInRotateArray(arr)