154. Find Minimum in Rotated Sorted Array II
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:
- [4,5,6,7,0,1,4] if it was rotated 4 times.
- [0,1,4,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].
Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.
You must decrease the overall operation steps as much as possible.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
int binarySearch(vector<int>& nums, int l, int r) {
if(l + 1 >= r) return min(nums[l], nums[r]);
int m = (l + r) / 2;
if(nums[l] < nums[m]) {
if(nums[m] > nums[r]) return binarySearch(nums, m, r);
return binarySearch(nums, l, m);
}
if(nums[l] == nums[r]) {
if(nums[m] > nums[r]) return binarySearch(nums, m, r);
if(nums[r] == nums[m]) return min(binarySearch(nums, l, m), binarySearch(nums, m, r));
return binarySearch(nums, l, m);
}
if(nums[m] >= nums[r]) return binarySearch(nums, m, r);
return binarySearch(nums, l, m);
}
public:
int findMin(vector<int>& nums) {
return binarySearch(nums, 0, nums.size() - 1);
}
};
|
