在做题中学习(53): 寻找旋转数组中的最小值

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

解法：O(logn)->很可能就是二分查找

思路：再看看题目要求，可以画出旋转之后数组中元素的大小关系：

首先，数组是具有二段性的(适配二分查找)，因为原来的有序数组旋转元素挪到前面后，一定比后面的元素都要大，所以由此可以画出上图。

细节

1.以D为参照 ，判断mid落在[A,B],还是[C,D]区间内，最后如果求出[C,D]区间的左端点，也就是C，就知道了最终结果的下标。

2.以A为参照，那么最后一次旋转的元素变成数组首元素，也就是[A,B]最小的元素，但比[C,D]区间的值都要大，所以也是一种思路。[A,B]区间的值 >A,[C,D]区间的值 <A，其实还是求[C,D]区间的左端点。

3.以A为参照点时，考虑边界情况：旋转后 和 原数组 相同，那么数组首元素 > 尾元素。因为A为参照点时，是以首元素为参照，如果命中 nums[mid] >= sub 条件，则会越过最小元素。

上述两种参照点都可以解决问题，代码也都会给在下方，但注意：

根据在做题中学习（49）：排序数组中查找元素的第一个和最后一个位置-CSDN博客

中有更详细的求左区间的讲解和细节问题。

1.以A为参照

class Solution 
{
public:
    int findMin(vector<int>& nums) 
    {
        if(nums[0] < nums[nums.size()-1])
            return nums[0];

        int left = 0,right = nums.size()-1;
        int sub = nums[0];
        while(left < right)
        {
            int mid = left + (right - left) /2;
            if(nums[mid] >= sub)
                left = mid + 1;
            else if(nums[mid] < sub)
                right = mid;
        }        
        return nums[left];
    }
};

2.以D为参照

class Solution 
{
public:
    int findMin(vector<int>& nums) 
    {
        int left = 0,right = nums.size()-1;
        int back = right;
        while(left < right)
        {
            //求区间左端点
            int mid = left + (right - left) /2;
            if(nums[mid] > nums[back])
                left = mid + 1;
            else if(nums[mid] <= nums[back])
                right = mid;
        }
        //走到这里，left == right
        return nums[left];
    }
};