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

一、题目描述

已知一个长度为?n?的数组，预先按照升序排列，经由?1?到?n?次?旋转?后，得到输入数组。例如，原数组?nums = [0,1,2,4,5,6,7]?在变化后可能得到：

• 若旋转?4?次，则可以得到?[4,5,6,7,0,1,2]
• 若旋转?7?次，则可以得到?[0,1,2,4,5,6,7]

注意，数组?[a[0], a[1], a[2], ..., a[n-1]]?旋转一次?的结果为数组?[a[n-1], a[0], a[1], a[2], ..., a[n-2]]?。

给你一个元素值?互不相同?的数组?nums?，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的?最小元素?。

你必须设计一个时间复杂度为?O(log n)?的算法解决此问题。

二、题目解析

本题也是典型的自身数组顺序不是有序，但是仍然去寻找二段性去解决。

我们根据旋转数组的特性去抽象数据的范围如下：

我们要求的最小值就是C点，上图明显给我们二段性的提示，我们比较的基准就是D点。

这样我们就可以套入二分的模板去解决。

三、原码

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int len = nums.size();
        int right = len-1;
        int mid = 0;
        while(left < right)
        {
            mid = left + (right-left)/2;
            if(nums[mid] < nums[len-1])//将数组的最后一个元素作为参考值
                right = mid;
            else
                left = mid+1;
        }
        return nums[left];
    }
};