把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
说白了就是寻找数组里面的最小值，但是如果像下面第一个这样写，虽然可以实现功能，但是在现场手撕代码时候肯定拿不到offer的
class Solution: def minNumberInRotateArray(self, rotateArray): # write code here if not rotateArray: return 0 else: return min(rotateArray)
class Solution: def minNumberInRotateArray(self, rotateArray): # write code here '''考虑三种情况： 1.数组为空数组，此时规定返回值为0 2.数组中只有一个元素，那么无需做任何比较，此时最小值就是该元素 3.数组中元素多于1个的情况''' if(rotateArray==[]): return 0 i=0 if(i==len(rotateArray)-1): return rotateArray[0] '''考虑到数组本身非递减，那么可以想见的是，旋转数组包含两个子数组，子数组内本身有序，只要将向量两个元素 之间进行比较，如果前者大于后者，那么可见这是两个子数组的分界点，比如[3,4,5,1,2],内含两个有序子数组[3,4,5] 和[1,2],子数组本身内部非递减，那么找到转折点，就是数组内部最小元素''' while(i<len(rotateArray)-1): if(rotateArray[i]<=rotateArray[i+1]): i+=1 else: return rotateArray[i+1]
当时当数组比较长度比较大时，第二种方法的比较次数其实取决于子数组的长度，考虑到这一缺点，引入下面的的一个二分法
（1）我们用两个指针left,right分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则，第一个元素应该是大于最后一个元素的（没有重复的元素）。
但是如果不是旋转，第一个元素肯定小于最后一个元素。
（2）找到数组的中间元素。
中间元素大于第一个元素，则中间元素位于前面的递增子数组，此时最小元素位于中间元素的后面。我们可以让第一个指针left指向中间元素。
移动之后，第一个指针仍然位于前面的递增数组中。
中间元素小于第一个元素，则中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素。
移动之后，第二个指针仍然位于后面的递增数组中。
这样可以缩小寻找的范围。
（3）按照以上思路，第一个指针left总是指向前面递增数组的元素，第二个指针right总是指向后面递增的数组元素。
最终第一个指针将指向前面数组的最后一个元素，第二个指针指向后面数组中的第一个元素。
也就是说他们将指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这就是循环的结束条件。
# -*- coding:utf-8 -*- class Solution: def minNumberInRotateArray(self, rotateArray): length = len(rotateArray) if length == 0: return 0 if length == 1: return rotateArray[0] '''left，right分别指向，数组的第一个和最后一个位置''' left, right = 0, length- 1 ''' 可以想见的是，如果一个数组的长度大于二，那么left=0，left<right，当数组中只剩下一个元素时，left=right 此时显然最小元素就是rotateArray[left],其实就是一步步切割数组，逼近数组中元素最小的那个值，二分法这一思想其实很常见，我们平时猜数字，也是一步步确定
目标值所在范围，最后只剩下一个元素时，确认即为该值 以[4,5,6，7，1,2，3]为例，一定要明确旋转数组本身的特性： 1）这个旋转数组本身是包含两个内部有序非递减的子数组 2）数组第一个元素一定比最后一个元素大1 第一次循环，left=0,right=6,mid=3,rotateArray[3] > rotateArray[6],说明，rotateArray[3],rotateArray[6]不在一 个递增数组内部，结合旋转数组的特性，数组的最小元素应该在[mid+1,right]之间寻找 第二次循环，此时left=4,right=6,mid=5,rotateArray[5] < rotateArray[6],说明此时rotateArray[5]属于一个递增数组 内部，最小值应该在[left,mid]之间寻找，那么赋值，令right=mid,此时left=4,right=mid=5，仍满足left<right 进入第三次循环，mid=(left+ right) >> 1,mid=4，left=4,right=5，rotateArray[4] < rotateArray[5]，说明rotateArray[4] ， rotateArray[5]属于一个递增数组内部，那么最小值应该在[left,mid]之间，再次赋值，right=mid=4,此时left=4 left此时等于right,跳出循环，元素最小值就是rotateArray[4] ''' while left< right: mid = (left+ right) >> 1 if rotateArray[mid] > rotateArray[right]: left = mid+ 1 elif rotateArray[mid] <= rotateArray[right]: right = mid return rotateArray[left]