剑指Offer（六）

旋转数组的最小数字

题目描述：

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

解题思路：

利用二分法进行查找，如果中间的数小于数组第一位，那么可以把中间数的后面部分全部砍掉，中间数变成最后一位；如果中间的数大于数组最后一位，那么把前面部分全部砍掉，中间的数变为第一位，一直循环到只剩两个数，最后比较一下得到最小的数。

代码如下：

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        if not rotateArray:
            return 0
        if len(rotateArray)==1:
            return rotateArray[0]
        first=0
        last=len(rotateArray)-1
        mid=(first+last)/2
        while (first+1)<last:
            if rotateArray[mid]<rotateArray[first]:
                last=mid
            if rotateArray[mid]>rotateArray[last]:
                first=mid
            mid=(first+last)/2
        return min(rotateArray[mid],rotateArray[mid+1])
        # write code here