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

这题常规使用二分查找来解，这里先皮一下，直接用set初始化函数排序，两行代码秒解。同理也可以直接用sort函数排序，也是两行解。

ps: 使用set函数初始化的运行速度和使用sort排序的时间基本一致，都是超过95%www。空间复杂度上当然sort更优。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        set<int> s(rotateArray.begin(),rotateArray.end());
        return *s.begin();
    }
};

言归正传，下面讲解一下二分查找的解法。
首先先从简单的情况出发，假设原数组中无重复数字，由题目知该数组为升序数组旋转后得到。那么该数组必定可以分为两部分，左边部分和右边部分都是一个升序数组，而其中间分隔处的点就是要寻找的最小值点。
那我们使用二分查找的条件就很明确，若左数left比中心数mid小，说明mid仍处在左边部分的升序数组中，使查找范围右缩，left = mid。当left大于等于mid时，若右数right比mid大，则说明mid处在右边部分的升序数组中，使查找范围左缩，right = mid。当以上条件均不满足，即left大于等于mid，right小于等于mid时，返回left和right中的小值，即为最小值。
二分查找的一个特点是，根据需求的不同，细节会发生许多变化，这里也一样。在基本的二分查找寻找目标数时，一般移动left与right是

left = mid + 1;
right = mid - 1

而本题中使用了

left = mid;
right = mid

原因是，寻找目标数中可以通过判断是否等于目标数，

target == arr.at[mid]

来将mid排除到查找范围之外，而本题中不行。本题中寻找的最小值是一个未知数，你无法判断当前的mid是否就是你要寻找的数，故不能将mid排除在搜索范围之外。

代码写到这里时，题目提供的两个测试用例都无事通过了，还是一样的剧本，自信满满点下提交，用例未通过光速吃瘪。
上面的代码忽略了一个重要的问题，重复数字。当数字重复时，上面的判断逻辑将被完全打乱。这也就是为什么会出现开头那个用set的构造函数解题的代码了w。
当我看到重复数的时候，第一反应就是去重，提到去重条件反射就会想到set。但是本题显然不能使用set来解，那就只能手动去重。
当重复数字位于数组中时，这显然不会干扰我们写好的判断逻辑，因为此时它们仍处在同一个升序数组中，没有改变我们前提假设的条件。
而当重复数字出现在数组的头部和尾部时，就可能出现问题，使得得判断逻辑出错。因为二分查找最开始是通过头尾元素得出mid，然后用mid与头尾元素进行比较，若left与right相等，则会直接跳出循环，返回一个错误的结果。所以需要对left进行优化，开始时比较left元素与队尾元素，若想等，则left++，直到不等或left=right。这样做只有两个结果，若最后left=right，则整个数组只有一个数字，返回任意一个数，若最后left!=right，则开头的重复元素已被去除，整体判断逻辑可以正常运行。
这里还有一种情况，就是数组是开头的重复元素，加上后面只有一个升序数组的结构。比如{3,3,1,2,3}，这种情况也不符合我们提前假设好的情况，所以也需要排除。实际操作也比较简单，排除完开头的重复元素后，将left与队尾元素进行比较，若其比队危元素小，则直接返回left。因为我们知道，按照我们提前假设的条件，数组分为左右两个升序数组，那么左边是一定比右边大的，若左边比右边小了，那么显然它只有一个升序数组。

感觉自己这道题还没有吃透，欢迎大家一起讨论研究。

ps: 使用set构造函数，使用sort排序，以及使用下面这种二分查找的时间复杂度基本一致，都是超过95%。而空间复杂度上二分查找有绝对优势，set构造函数超过30%，sort超过50%，二分查找超过85%。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int left = 0;
        int right  = rotateArray.size() - 1;
        while(left < right && rotateArray.at(left) == rotateArray.back()){
            left++;
        }
        if(left == right){
            return rotateArray.at(left);
        }
        if(rotateArray.at(left) < rotateArray.at(right)){
            return rotateArray.at(left);
        }
        while(left < rotateArray.size() && right >= 0 && right > left){
            int mid = left + (right - left)/2;
            if(rotateArray.at(left) < rotateArray.at(mid)){
                left = mid;
            }
            else if(rotateArray.at(right) > rotateArray.at(mid)){
                right = mid;
            }
            else{
                break;
            }
        }
        return rotateArray.at(left) < rotateArray.at(right) ? rotateArray.at(left) : rotateArray.at(right);
    }
};