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.
You may assume no duplicate exists in the array.
Solution
Binary-search, time O(logn), space O(1)
由于mid有可能跟left相等，但一定小于right，所以用nums[mid]和nums[right]的比较作为条件比较方便，不用考虑相等的情况。具体解释如下。
- loop is left < right, which means inside the loop, left always < right
- since we use round up for mid, and left < right from (1), right would never be the same as mid
- Therefore, we compare mid with right, since they will never be the same from (2)
- if nums[mid] < nums[right], we will know the minimum should be in the left part, so we are moving right.
We can always make right = mid while we don’t have to worry the loop will not ends. Since from (2), we know right would never be the same as mid, making right = mid will assure the interval is shrinking. - if nums[mid] > nums[right], minimum should be in the right part, so we are moving left. Since nums[mid] > nums[right],mid can’t be the minimum, we can safely move left to mid + 1, which also assure the interval is shrinking
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) { // min could be min
right = mid;
} else { // mid couldn't be min
left = mid + 1;
}
}
return nums[right];
}
}
