Suppose a sorted array 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.
Example
Example 1:
Input：[4, 5, 6, 7, 0, 1, 2]
Output：0
Explanation：
The minimum value in an array is 0.
Example 2:
Input：[2,1]
Output：1
Explanation：
The minimum value in an array is 1.
代码
Approach #1 Binary Search
public class Solution {
public int findMin(int[] nums) {
if (nums.length == 1) return nums[0];
int left = 0, right = nums.length - 1;
if (nmus[right] > nums[0]) return nums[0];
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid - 1] > nums[mid]) {
return nums[mid];
}
if (nums[mid] > nums[0]) { // 和 nums[0] 比较
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
Approach 2:
class Solution {
public int findMin(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int start = 0, end = nums.length - 1;
int target = nums[nums.length - 1]; // 和最后一个数字比较
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
end = min;
} else {
start = mid;
}
}
return Math.min(nums[start], nums[end]);
}
}