面试题11：旋转数组的最小数字

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

解题思路：看到这道题首先的朴素想法是依次遍历数组，然后将最小数字得出，但是显然这种算法没有用到旋转数组的特性，因此需要进一步考虑。题目中给出的数组是一定程度上有序的，因此考虑运用二分查找法来解决这道考题。

思考如下：
1.首先考虑一般的过程，对于一个部分有序的数组，首先指定两个指针将p1指定为首指针，p2指定为尾指针，然后指定mid指针，可以将旋转数组看成两个递增的子数组，mid为首尾指针的中间位置，如果p1位置的元素大于等于p2位置的元素，此时进行判断：

①如果mid位置的元素大于或者等于p1指针对应位置的元素，则说明其元素属于第一个递增数组，将p1指针移动到mid位置，缩小搜索最小数字的范围，然后继续；
②如果mid位置的元素小于或者等于p2指针对应位置的元素 ，则说明其元素属于第二个递增数组，将p2指针移动到mid位置，说明对应的最小数字在mid位置前面的元素中；

结束条件 ：p2-p1==1，即两个指针相邻，说明p1为第一个递增子数组的最后一个元素位置，p2为第二个子数组的第一个元素，则返回最小的数字为p2位置对应的元素。

2.特殊情况：
如果将首位的0个元素放到后面，即原数组也是其中的一个旋转数组，此时p1位置的元素小于p2位置的元素，因此如果一开始首位的元素小于末尾的元素说明这是一个递增的数组，故最开始赋值的时候将mid赋值为p1即可。因为不满足循环条件会直接返回mid元素。

特殊情况2:如果mid==p1==p2对应位置的元素，则无法再缩小搜索范围，因此需要按照顺序进行查找最小的元素。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray)<= 0:
            return 0
        p1 = 0
        p2 = len(rotateArray)-1
        mid = p1
        while rotateArray[p1] >= rotateArray[p2]:
            mid = int((p1+p2)/2)
            if rotateArray[p1] == rotateArray[mid] and rotateArray[p2]==rotateArray[mid]:
                return self.Findmin(rotateArray,p1,p2)
            if p2-p1 == 1:
                mid = p2
                break
            if rotateArray[mid] >= rotateArray[p1]:
                p1 = mid
            elif rotateArray[mid] <= rotateArray[p2]:
                p2 = mid
        return rotateArray[mid]
    def Findmin(self,rotateArray,p1,p2):
        result = rotateArray[p1]
        for i in range(p1+1,p2+1):
            if rotateArray[i] < result:
                result = rotateArray[i]
        return result

结果：

牛客网运行结果.png