题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

输入一个升序的数组的一个旋转，输出旋转数组的最小元素。

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

数组可能包含重复项。

注意：数组内所含元素非负，若数组大小为0，请返回-1。

样例

输入：nums=[2,2,2,0,1]

输出：0

思路

这个问题是搜索问题，可以直接遍历找出最小的元素，但时间复杂度为$O(n)$。但这个问题可以用二分来做。那么首先要明确如何缩小范围。比较直观的想法是，我们要找的范围具有以下特征：数组范围内第一个元素大于数组范围内的最后一个元素。

给定一个数组有两种情况

• 第一种情况是数组旋转为0，此时数组完全有序，第一个元素即最小元素。
• 第二种情况是数组旋转不为0，此时数组表现出我们总结出来的特征，即数组范围内第一个元素大于数组范围内的最后一个元素，这时我们把数组二分，找到具有指定特征的子数组，再二分……直到找到一个范围内完全有序的数组或者搜索范围缩小到一点。

给定一个数组，根据以下步骤对数组进行搜索

1. 开始的索引lo是否小于结束索引hi
   - 若小于，说明搜索范围正常；
   - 若不小于，则说明搜索范围已经收缩到一点了，此时跳出循环步骤，返回第一个元素。

2. 该范围的数组是否完全有序（即第一个元素是否小于最后一个元素）
   - 若有序，说明我们要找的最小元素在此数组或者子数组中，只需返回排序最小的元素即可（第一个元素）；
   - 若无序（即nums[lo] > nums[hi]），则需要将数组二分然后继续寻找

3. 算出中间元素的索引值，此时数组划分为【lo…mid…hi】，此时数组分成的两个子数组中有一个满足指定的特征。
   - 若nums[lo] < nums[mid]，此时说明我们要找的数不在s—mid的范围内。因为不满足我们指定的特征，此时缩小范围（lo = mid + 1）；
   - 若nums[lo] > nums[mid]，满足我们指定的特征，所以缩小范围到此子数组（ hi = mid）；
   - 若nums[lo] == nums[mid]，此时[lo, mid]之间的数是相同的，此时无法进行二分，因为我们不知道最小的数是否在这个范围内，所以将这些重复的数减掉，做法是lo++(因为这个范围可能是一个点，如果直接将lo替换为mid，会出现死循环)。

4. 返回第一步

代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        auto len = nums.size();
        if(len == 0 ) return -1;
        int lo = 0, hi = len - 1;

        while(lo < hi) {
            if(nums[lo] < nums[hi]) break;
            int mid = lo + (hi - lo) / 2;
            if(nums[lo] < nums[mid]) lo = mid + 1;
            else if(nums[lo] > nums[mid]) hi = mid;
            else lo++;
        }
        return nums[lo];
    }
};