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

//假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。 
//
// 请找出其中最小的元素。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,4,5,1,2]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：nums = [4,5,6,7,0,1,2]
//输出：0
// 
//
// 示例 3： 
//
// 
//输入：nums = [1]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 5000 
// -5000 <= nums[i] <= 5000 
// nums 中的所有整数都是 唯一 的 
// nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转 
// 
// Related Topics 数组 二分查找 
// 👍 357 👎 0

/*
* 153 寻找旋转排序数组中的最小值
* 2021-02-26 15:40:53
* @author oxygenbytes
*/ 
#include "leetcode.h" 
//leetcode submit region begin(Prohibit modification and deletion)
class Solution2 {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        if(!n) return 0;

        if(nums[n-1] > nums[0]) return nums[0];

        while(--n){
            if(n >= 0 && nums[n] == nums[0]) n--;
            else break;
        }

        int l = 0, r = n;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] < nums[0]) r = mid; // 注意这里的特征，是nums[mid] < nums[0]
            else l = mid + 1;
        }
        return nums[l];
    }
};

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] <= nums.back()) r = mid; // 注意特征
            else l = mid + 1;
        }
        return nums[r];
    }
};
//leetcode submit region end(Prohibit modification and deletion)