题目来源
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
The array may contain duplicates.
一开始做的题目呢，是没有重复的数组，用直接遍历的话显然是不行的，会超时。那就二分查找吧，这个想法也很自然嗯嗯。不考虑重复元素的话直接如下就下可以了。因为没有重复元素，所以当nums[mid] == nums[l]的时候，实际上就相当于mid == l。
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0, r = n - 1, mid = 0;
while (l < r) {
if (nums[l] < nums[r])
return nums[l];
mid = (l + r) / 2;
if (nums[mid] >= nums[l])
l = mid + 1;
else
r = mid;
}
return nums[l];
}
};
假如数组中存在重复元素的话，那么对于nums[mid] == nums[l]的情况呢，我是直接把l加1。反正l加1之后最小值肯定还是在l到r之间的，代码如下：
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0, r = n - 1, mid = 0;
while (l < r) {
if (nums[l] < nums[r])
return nums[l];
mid = (l + r) / 2;
if (nums[mid] > nums[l])
l = mid + 1;
else if (nums[mid] == nums[l])
l = l + 1;
else
r = mid;
}
return nums[l];
}
};
