Find Minimum in Rotated Sorted Array
This problem is a series problems that have a little difficulty. The main difficulty not only exists in thinking of the idea to solve it, but also in implementing it correctly with out bug. The solution to this series of problems makes use of the same idea as binary search, so it is very important to handle search boundary correctly to avoid infinite looping and wrong answer.
No duplicated elements
If there is no duplicated elements in the array, the program will be much like that of binary search. In this case, we have only one minimal element . At first we pick a boundary and and make sure . Let , if , we know that , or there must have . To avoid infinite looping, we have to keep:
- After each iteration, we still have .
- After each iteration, is less than before
We let when and let when otherwise. As there always be when , so will become less and less and the loop must have an end.
public class FindMiniumInRotatedSortedArray {
public int findMin(int[] nums) {
int l = 0;
int r = nums.length - 1;
int mid;
while (l < r) {
mid = (l + r) / 2;
if (nums[mid] < nums[r]) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l];
}
}
Allow duplicated elements
If duplicated elements is allowed, the problem becomes a little more complex and we cannot implement it without recursion. The reason is that, if , the minimal number may appears both in or . The cases is also a little more difficult to discuss. we disscuss all cases below:
- : the same as before, the minimal element must be in
- : the same as before, the minimal element must be in
- : there are several different cases respect to different relationship between
and
- : both and is possible.
- : must be in
- : must be in
We find that the only difference comes when , and if , we should put union into the case of . So the solution is:
public class FindMiniumInRotatedSortedArray {
private int findMin(int[] nums, int l, int r) {
if (l >= r) return nums[l];
int mid = (l + r) / 2;
if (nums[mid] == nums[r] && nums[mid] == nums[l]) {
return Math.min(findMin(nums, l, mid), findMin(nums, mid + 1, r));
} else if (nums[mid] <= nums[r]) {
return findMin(nums, l, mid);
} else {
return findMin(nums, mid + 1, r);
}
}
public int findMin(int[] nums) {
return findMin(nums, 0, nums.length - 1);
}
}