专题三寻找旋转排序数组中的最小值

1.题目

题目分析：

给一个数组，然后这个数组可能是旋转过的，旋转是把最后一位放到前面，转一次就移动一次，找到最小值，并返回。

2.算法原理

假设[3,4,5,1,2]旋转后的数组，用折线图画出来，就可以看到二段性的特征，则使用二分查找来解决，需要找一点来作为判断基准，则取最后位置点来判断，有三种情况，一直递增，和最后一个最小，以及正常旋转一半，最后一点都可以很好处理，如果取的中间值小于等于最后一个值，就把right=mid，这里有等于情况是因为旋转一半情况下，在CD区域的话是有可能刚好是最小值，AB段是没有最终值的，有等于情况就直接righ=mid，另一个就是left=mid+1，避免死循环，以及mid的计算不用加+1，也是避免死循环。

3.代码实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left=0,right=nums.size()-1;
        int x=nums.size()-1;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(nums[mid]<=nums[x]) right=mid;
            else left=mid+1;
        }
        return nums[left];
    }
};