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.
Solution1：二分查找
思路： Always the MIN find in the rotated part
屏幕快照 2017-09-04 下午3.37.15.png
Time Complexity: O(logN) Space Complexity: O(1)
Solution2：Binary Search Template Round1
加corner case对于没有rotated的情况
Solution1 Code：
class Solution {
public int findMin(int[] nums) {
int start = 0, end = nums.length - 1;
while (start < end) {
// for un-rotated array
if (nums[start] < nums[end])
return nums[start];
int mid = (start + end) / 2;
// always find in the rotated part
if (nums[mid] >= nums[start]) {
start = mid + 1;
} else {
end = mid;
}
}
return nums[start];
}
}
Solution2 Code：
class Solution {
public int findMin(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int left = 0, right = nums.length - 1;
// corner case
if(nums[left] < nums[right]) {
return nums[left];
}
while(left + 1 < right) {
int mid = left + (right - left) / 2;
if(nums[left] < nums[mid]) {
// left normal
left = mid;
}
else {
// right normal
right = mid;
}
}
return nums[right];
}
}
