二分
旋转数组会形成两段升序序列,其中第一段的最小元素(即nums[0])一定大于等于第二段的最大元素(即nums[n])。利用二分找到某个小于nums[0]的数的下标mid,那么目标最小值的下标就落在[0, mid]区间内。
注意:如果第二段序列中nums[n]等于nums[0],需要删除尾部元素直到第二段严格递增。
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size() - 1;
if(n == -1) return n;
while(n > 0 && nums[n] == nums[0]) n--;
if(nums[0] < nums[n]) return nums[0];
int l = 0, r = n;
while(l < r){
int mid = l+r >> 1;
if(nums[mid] < nums[0]) r = mid;
else l = mid + 1;
}
return nums[l];
}
};