Find Minimum in Rotated Sorted Array
Suppose a sorted array 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
根据中间与两边的大小来判断最小值在哪里
Complexity
时间复杂度 O(logn),空间复杂度 O(1)
Code
public class Solution {
public int findMin(int[] num) {
if (num.length == 0) return 0;
int left = 0, right = num.length -1;
while (left < right && num[left] > num[right]) {
int mid = left + (right - left) / 2;
if (num[mid] > num[right]) left = mid + 1;
else right = mid;
}
return num[left];
}
}
如果有重复
public class Solution {
public int findMin(int[] num) {
if (num.length == 0) return 0;
int left = 0, right = num.length -1;
while (left < right && num[left] >= num[right]) {
int mid = left + (right - left) / 2;
if (num[mid] > num[right]) left = mid + 1;
else if (num[mid] < num[right]) right = mid;
else left++;
}
return num[left];
}
}