题目

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

思路

  1. 利用二分查找算法，每次的mid与右端点进行比较
  2. 把数组分为空、长度为1、长度大于等于2的三种情况.
  3. 先将长度大于2的进行循环查找使得最终的正确答案在较短的数组中,然后数组为空是一种，长度为1是一种，长度为2是一种。

代码

  1. #考虑非递减
  2. class Solution:
  3.     def __init__(self):
  4.         self.ro=[]
  6.     def minNumberInRotateArray(self,rotatearray):
  7.         self.ro=rotatearray
  8.         while len(self.ro)>2:
  9.                 mid=len(self.ro)//2
  10.                 if self.ro[mid]>self.ro[-1]:
  11.                     self.ro=self.ro[mid+1:]
  12.                 else:
  13.                     self.ro=self.ro[:mid+1]                    
  14.         if len(self.ro)==0:
  15.             return 0
  16.         elif len(self.ro)==1:
  17.             return self.ro[0]
  18.         else:
  19.             if self.ro[0]>self.ro[1]:
  20.                 return self.ro[1]
  21.             else:
  22.                 return self.ro[0]

非常注意的点

  1. 注意题中给出的提示，如果数组长度为0，或长度为1要单独考虑
  2. 循环过程中，最后正确答案落在数组中，数组长度可能为1，也可能为2
  3. mid=len(self.ro)/2 向下取整正好可以当作索引
  4. 循环过程中，如果mid大于右端点，则取右侧；如果mid小于右端点，则取左侧包含临界点；如果mid等于右端点那么右侧值全部相等，这时取左侧包含临界点。