题解 | #旋转数组的最小数字#

利用二分查找的思想。旋转数组可以分为两个部分，这两个部分分别都是不减的，但这两个部分中间的2个元素是经历了一个减的过程。考虑到这是一个有序数组旋转出来的，举例：【1 2 3 4 4 5 6】，可以旋转成【3 4 4 5 6 1 2】，这时候左面一半一直增大，右边先增大再从最小重新增大。既然是二分法，就选择中值5，可以看到左边的端点小于中值，右边的则是中值比端点值大。所以我们就是要找一个左大右小的区间然后继续这个查找。

如果是【1 3 3 3 6】，旋转为【6 1 3 3 3】，那我们可以让right减一，重新循环，因为我们知道从最大到最小这个过程肯定不出现在连续相同的点。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        size_t left=0,right=rotateArray.size()-1,mid=0;
        int temp;
      //处理特殊情况，容量比较小的情况下直接出结果
        if(right==0)return rotateArray[0];
        if(right==1)return min(rotateArray[0],rotateArray[1]);
        while(left!=right){
            mid=(left+right)/2;
          //mid>right意味着右半段出现了跳变，<意味着右半段是从小到大正常的，那就意味着跳变出现在左边
            if(rotateArray[mid]>rotateArray[right])left=mid+1;
            if(rotateArray[mid]<rotateArray[right])right=mid;
            if(rotateArray[mid]==rotateArray[right]&&mid!=right)right--;
        }
        return rotateArray[left];
    }
};