8、旋转数组中的最小数字

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

根据数组的性质，可以按照二分查找的思想来确定结果
基本功能：先比较中间元素与开头元素的大小，如果比开头元素大，那么最小元素就在后半部分。反之，则在前半部分。
如此循环下去，最终当index1 - index2 = 1时，此时index2指向的就是所要查找的最小元素。

特殊情况1：

因此在一开始的while循环前，将indexMid初始化为index1，当index1指向的元素小于index2指向的元素时，就说明本身就是一个有序数组，不需要查找，此时直接返回indexMid即可。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0

        index1 = 0
        index2 = len(rotateArray) - 1
        indexMid = index1
        #若此时index1小于index2，那么就不用循环，返回此时的indexMid即可
        while rotateArray[index1] >= rotateArray[index2]:
            if index2 - index1 == 1:
                indexMid = index2
                break

            indexMid = (index1 + index2) // 2
            if rotateArray[indexMid] >= rotateArray[index1]:
                index1 = indexMid
            else:
                index2 = indexMid

        return rotateArray[indexMid]

ser = Solution()
print(ser.minNumberInRotateArray([3,4,5,1,2]))

以上代码没有考虑以下的特殊情况。

特殊情况2：
当最开始，开头元素，中间元素与最后的元素都相等时，此时没法判别哪个大哪个小，因此只能顺序查找了。