参考“33. 搜索旋转排序数组”。
只二分两段升序序列组成的一个序列,且第一段升序序列中的每个元素均大于第二段升序序列中的每个元素的序列。整个序列为升序序列,即a[a.length - 1] > a[0],则返回a[0] 即可。
当a[mid] < a[0] 时,r = mid,即最小值一定在 [l, mid] 之间。
当a[mid] ≥ a[0] 时,l = mid + 1,即最小值一定在 [mid + 1, r] 之间。
当只剩两个元素时,必有a[0] > a[1] ,而mid = l + r >> 1 = l,a[mid] ≥ a[0] ,l = mid + 1 = r,即最小值为a[1] 。
时间复杂度:O(logn) ;空间复杂度:O(n) 。
class Solution {
public int findMin(int[] nums) {
if (nums[nums.length - 1] > nums[0]) {
return nums[0];
}
int l = 0, r = nums.length - 1, mid;
while (l < r) {
mid = l + r >> 1;
if (nums[mid] < nums[0]) {
r = mid;
} else {
l = mid + 1;
}
}
return nums[l];
}
}
当a[mid] > a[0] 时,l = mid,即最小值一定在 [mid, r] 之间。
当a[mid] < a[0] 时,r = mid - 1,即最小值一定在 [l, mid) 之间。
当只剩两个元素时,必有a[0] > a[1] ,而mid = l + r + 1 >> 1 = r,a[mid] < a[0] (a[mid] 不可能等于a[0]),r = mid - 1,即最小值为a[l + 1] 。
class Solution {
public int findMin(int[] nums) {
if (nums[nums.length - 1] > nums[0] || nums.length == 1) {
return nums[0];
}
int l = 0, r = nums.length - 1, mid;
while (l < r) {
mid = l + r + 1 >> 1;
if (nums[mid] > nums[0]) {
l = mid;
} else {
r = mid - 1;
}
}
return nums[l + 1];
}
}