面试题 11：旋转数组的最小数字.md

试题链接：22. 旋转数组的最小数字 - AcWing题库

方法一：二分法

• 思路：旋转后的数组实际上可以划分为两个排序的子数组，前面子数组的元素都大于或者等于后面的子数组（除了旋转 0 个数组这种特殊情况）。我们让第二个子数组的元素都严格小于第一个子数组的元素，因为当二分取的中间数等于两边的数时，无法区分向哪个区间缩小，因此去掉第二个子数组尾部同第一个子数组首个元素相同的部分，如果第二个子数组被全部去掉，则最小的元素为第一个子数组的首元素，这种情况同选择 0 个数组的情况一样。排除重复元素后二分就简单了，判断中间元素是否小于首元素，如果小于就说明在第二个子数组，最小值在左侧或就是当前位置，区间缩小到 [l, mid] ，否则区间缩小到 [mid + 1, r]。
• 时间复杂度：平均 O(logn)，最坏 O(n)
• 空间复杂度：O(1)

class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return -1;
        }
        
        while (nums[0] == nums[n - 1]) n--;
        
        if (nums[0] < nums[n - 1]) return nums[0];
        
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < nums[0]) r = mid;
            else l = mid + 1;
        }
        
        return nums[l];
    }
};