题意

原数组为一个非递减的序列，将前若干个数字一起移动到末尾。给你一个移动后得到的数组，返回数组中最小的数。数组长度为0则返回0.
例如：
原数组为 [1,2,3,4,5]
将[1,2,3]移动到数组后得到旋转数组
[4,5,1,2,3]

一般思路

设一个变量mins存最小值，遍历一遍数组比较得到最小值，因此时间复杂度O(n)。

方法伪代码

int mins = nums[0];
for(int i = 1; i < nums.size(); i ++ )
    mins = min(mins,nums[i]);
return mins;

二分思路

一般情况下可以做到O（logn），最坏情况下还是O（n）。

一般情况分析

设原数组为[1,2,3,4,5],用图表示为，PS: n为数组最后一个数的下标

取前两个数即[1,2]移动到数组后面得到旋转数组[3,4,5,1,2],用图表示为

我们的目的是要找到虚线右边的递增序列中最低点，由图可以得知nums[0]即3是大于虚线右边所有的数且在虚线左边的上升序列中为最低点，所以若nums[mid]<nums[0]就表示mid在虚线右边上升序列中，答案就在[l,mid]之间，反之mid在虚线左边的上升序列中，答案就在[mid + 1,r]。

方法伪代码

int l = 0, r = n;
while(l < r)
    {
        int mid = l + r >> 1;
        if(nums[mid] < nums[0])
            r = mid;
        else
            l = mid + 1;
    }
return nums[r];

数组中存在重复的数

此时虚线左右两边有相等值，当nums[mid]落在这个值时就不能判断是落在虚线左边还是右边，将无法使用二分正确找到答案区间。
因此需要将虚线右边的横线即与nums[0]相等的值删除

int n = nums.size() - 1;
while(n > 0 && nums[n] == nums[0])
    n --;

此操作后就会变成一般情况，可以正常使用二分。

特殊情况

在上述去除相等值操作中存在一种特殊情况，虚线右边的数全部被删除。那这时候数组中最小的数就是nums[0]，直接返回即可。

完整代码

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if(!rotateArray.size())
            return 0;
        int n = rotateArray.size() - 1;
        while(n > 0 && rotateArray[n] == rotateArray[0])
            n --;
        if(rotateArray[n] >= rotateArray[0])
            return rotateArray[0];

        int l = 0, r = n;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(rotateArray[mid] < rotateArray[0])
                r = mid;
            else
                l = mid + 1;
        }
        return rotateArray[r];
    }
};