1. class Solution {
2. public:
3. int minNumberInRotateArray(vector<int> rotateArray) {
4. //常规的遍历方法时间是O(N)的，需要使用二分法，这样对于不重复的数组，就能实现O（logN）的时间
5. int l=0,r=rotateArray.size()-1;
6. if(r<0)return NULL;//空数组
7. int m=0;
8. while(l<r){
   //当左指针小于右指针的时候，继续二分法
9. //下面分两种情况讨论：①数组仍然具有旋转数组特性，②已经不是旋转数组了，变回递增数组，直接返回l
10. if(rotateArray[l]>=rotateArray[r]){
    //等号是为了考虑数组存在重复的情况
11. m=(l+r)>>1;
12. if(rotateArray[m]<rotateArray[r])//中间值小于右边，则中间值属于属于右边数组
13. //那么最小值是在 [l,m]之间
14. r=m;
15. else
16. if(rotateArray[m]>rotateArray[r])//中间值大于右边，中间值属于左边数组
17. //最小值在(m,r]之间
18. l=m+1;
19. else//如果中间值等于右边，无法判断，让l++ 或者让r--
20. l++;
21. }
22. else// 当l 小于r 的时候，l一定是最小值
23. break;
24. }
25. return rotateArray[l];
26. }
27. };