题目描述

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

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

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

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

示例 2:

输入: [4,5,6,7,0,1,2]
输出: 0

算法分析

二分套路多，分析完后就可以直接上模板了。下面是两个常用模板，具体对模板的理解和使用可以看看我写的 二分总结

模板一

int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}

模板二

int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

该题给了一个旋转后的排序数组，旋转前该数组由于是排序的，因此最小值就是第一个元素。但是现在由于旋转的缘故，该最小值被旋转到了数组的中间，根据下图可以清楚地看到，由于数组中没有重复元素，因此旋转后的数组出现了断层。在前半部分的所有数的大小都在断层之上，后一部分的值都在断层之下。也就是这一断层的出现，将我们的区间分成了两部分，其实前半部分都是大于最后一个元素的，后半部分都是小于等于最后一个元素的。而我们所要求解的最小值就是满足小于等于最后一个元素的右侧区间的左端点。分析到这，因此又是直接上模板。

C ++代码

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

        int l = 0, r = nums.size();

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

        return nums[r];

    }
};