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

NC71 旋转数组的最小数字

题意

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

1. 暴力做法（不合要求）

思路略。

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int res = INT32_MAX; // 求最小值，就初始化为最大值
        for (auto i : rotateArray) res = min(res, i);
        return res;
    }
};

时间复杂度： $O(n)$ ，遍历了一轮。
空间复杂度: $O(1)$

2. 二分查找

面试官：此题要求利用二分查找，把平均时间复杂度降低到 $logn$ 。
我：挠头，这也不是单调性呀~~，也不知道目标值是啥
面试官：好了我的问题问完了，你还有什么要问我的？

二分查找通常适用于数组对某种关系满足单调性的查找过程，但是本题似乎不满足题意。事实上，二分查找的本质是不断收敛答案区间，每次去掉一半即可。

这道题我们不知道要找的target是什么，但是我们发现有这样一个性质：

断层点右边的所有数，都比左侧的最小值小
断层点左边的所有数，都比右侧的最大值大

所以mid的分界性可以更灵活，不知道a[mid]和谁比，那么就自己设计比较策略。我们可以这样去比较(设当前迭代的区间是[l,r], mid为区间中点)：

如果a[l]<a[r], 说明已经收敛到一段单调递增区间，左端点即为所求。
如果a[mid]>a[l], 根据上面的性质推知[l, mid]是递增的，因此我们要找的最小值一定在mid右侧，mid也肯定不是，故收敛区间至[mid+1, r].
如果a[mid]<a[r], 同理知道[mid, r]是递增的，我们要找的值一定在mid左侧，注意这里，mid也有可能是答案，故收敛区间为[l, mid].
如果都不是，我们不知道答案在哪边，但可以知道l不是答案，否则可以进入情况3或情况1. 故收敛区间至[l+1, r].
最后l即为所求。

图解参考“Ariser.cn”的图示：
图片说明

图片说明

class Solution {
public:
    int minNumberInRotateArray(vector<int> a) {
        int l = 0, r = a.size()-1;
        while (l < r) {
            // l到r递增，那么l就是答案
            if (a[l] < a[r]) return a[l];

            int mid = (l+r)>>1; // 因为是l=mid+1类型的收敛，所以是下取整
            // 与左端点比较
            if (a[mid] > a[l]) l = mid+1;
            // 与右端点比较
            else if (a[mid] < a[r]) r = mid;
            // 不确定答案，至少l肯定不是答案
            else l++;
        }
        return a[l];
    }
};

时间复杂度：最差 $O(n)$ , 平均 $O(logn)$ . 平均每次区间收敛一半，而对于极端情形（例如全一样的数组），每次都走到l++的分支，所以最坏为线性。
空间复杂度： $O(1)$ . 没有定义额外的数组。