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

class Solution: """ 由于整个数组在一定程度上是有序的，因此可以借鉴二分查找的思想，达到接近O(logn)的时间复杂度。 将一个有序(升序)数组的前x个元素挪到末尾，这里可以分类进行讨论。 第一类：挪动元素个数为数组长度的整数倍，那么这时候等于没有挪动，最小值出现在idx=0 第二类：挪动元素个数不是数组长度的整数倍，那么这时候挪动后的数组可以分成两个子数组，其中左边子 数组的元素都是大于等于右边子数组的。 [3, 4, 5, 1, 2] 这时候我们维护两个指针p1和p2，分别指向左边子数组和右边子数组。当中间元素大于等于p1指向 的元素的时候，则中间元素属于左边子数组，反之属于右边子数组。 当两个指针相邻的时候p2就指向了右边子数组的第一个元素，也就是整个数组的最小值。 第三类：[1, 0, 1, 1, 1] 当p1和p2指向的元素和中间的元素相等的时候，这时候如果按照第二类的思路，那么会误判最小值 在中间元素之后，因此这种情况下我们需要顺序查找。 """ def minNumberInRotateArray(self, rotateArray): if not rotateArray: return 0 # 将mid初始化为0，可以处理第一类情况，因为这时不会进入循环，直接输出最小值 left, mid, right = 0, 0, len(rotateArray) - 1 while rotateArray[left] >= rotateArray[right]: # 如果left和right已经相邻，那么最小值就是right指向的元素 if left == right - 1: mid = right break mid = (left + right) >> 1 # 如果left, right, mid指向的元素都相等，那么需要对这个区间进行顺序查找，否则按照 # 第二类情况的解题思路会判断错误 if rotateArray[left] == rotateArray[mid] == rotateArray[right]: return min(rotateArray[left:right + 1]) # 中间元素在左半边，最小值出现在右边子数组[mid, right] if rotateArray[left] <= rotateArray[mid]: left = mid # 中间元素在右半边，最小值出现在左边子数组[left, mid] else: right = mid return rotateArray[mid]