LeetCode - Find Minimum in Rotated Sorted Array II
Problem description
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.
Example 1:
1
2
Input: [1,3,5]
Output: 1
Example 2:
1
2
Input: [2,2,2,0,1]
Output: 0
Note:
- This is a follow up problem to Find Minimum in Rotated Sorted Array.
- Would allow duplicates affect the run-time complexity? How and why?
Analysis
Just use the binary search.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public int findMin(int[] nums) {
return find(nums, 0, nums.length - 1);
}
int find(int[] nums, int l, int h){
if (nums[l] < nums[h]){
return nums[l];
}
if (h-l <= 1){
return Math.min(nums[l], nums[h]);
}
int mid = l + (h-l) / 2;
if (mid-1>=0 && nums[mid-1] > nums[mid]){
return nums[mid];
}
if (mid+1 < nums.length && nums[mid] > nums[mid+1]){
return nums[mid+1];
}
if (nums[mid] > nums[h]){
return find(nums, mid+1, h);
}
else if (nums[mid] < nums[h]){
return find(nums, l, mid-1);
}
else {
return find(nums, l, h-1);
}
}
}