题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]
输出: 1

示例 2：

输入: [2,2,2,0,1]
输出: 0

说明：

• 这道题是寻找旋转排序数组中的最小值 的延伸题目。
• 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

算法思路

该题在LeetCode 154. 寻找旋转排序数组中的最小值的基础上多了一个条件就是可能出现重复元素。在上一题中，我们发现由于没有重复元素的出现，在旋转后的数组会出现一个断层，很好地将区间一分为二。

而此题由于重复元素的出现，如果旋转后数组的首元素不等于尾元素，那么该题与上一题的做法完全一样。但是旋转后的数组很有可能前一部分元素等于后一部分元素值。那么为了能够继续像上一题那样利用二分求解，我们就必须想办法让我们二分区间里的数出现断层，因此我们可以将我们二分时的左边界移动到一个大于最后一个元素的值，那么我们就会发现此时求解方法与上题就一模一样了。

注意：由于重复元素的出现，极端情况下可能所有元素的值都是一样的，所以在移动左边界时需要防止左边界移动出界。

C++代码

class Solution {
public:
    int findMin(vector<int>& nums) {
        if(nums.empty()) return 0;

        int l = 0, r = nums.size()-1;
        while(nums[l] == nums.back() && l < r) l ++;

        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] <= nums.back()) r = mid;
            else l = mid + 1;
        }

        return nums[r];
    }
};