Leetcode153. Find Minimum in Rotated Sorted Array
旋转数组找最小值
其中数组中的值唯一
你可以顺序遍历，当然一般会让你用二分来搞
方法1
数组可以分成两部分，左边是 ≥ n u m s [ 0 ] \ge nums[0] ≥nums[0], 右边是 < n u m s [ 0 ] <nums[0] <nums[0]
换句话说就是找第一个 < n u m s [ 0 ] <nums[0] <nums[0]的元素
如果 > = n u m s [ 0 ] >=nums[0] >=nums[0]则往右边，否则左边
不过也需要排除有序的情况
class Solution {
public:int findMin(vector<int>& nums) {if(nums[0] <= nums.back())return nums[0];int n = nums.size();int l = 0, r = n - 1;while(l <= r){int mid = l + (r - l) / 2;if(nums[mid] >= nums[0])l = mid + 1;else r = mid - 1;}return nums[r + 1];}
};
方法2
依然二分
如果 n u m s [ m i d ] > n u m s [ r ] nums[mid]>nums[r] nums[mid]>nums[r]，那最小值肯定在右半边
如果 n u m s [ m i d ] ≤ n u m s [ r ] nums[mid]\le nums[r] nums[mid]≤nums[r], 那 n u m s [ m i d ] nums[mid] nums[mid]也可能称为最小，所以 r = m i d r = mid r=mid而不是 r = m i d − 1 r=mid-1 r=mid−1
与普通二分的区别就是退出条件要 l < r l<r l<r而不是 l ≤ r l\le r l≤r,不然你别想出去了
class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size();int l = 0, r = n - 1;while(l < r){int mid = l + (r - l) / 2;if(nums[mid] > nums[r])l = mid + 1;else r = mid;}return nums[r];}
};