LeetCode 153 - Find Minimum in Rotated Sorted Array

作者 QIFAN 日期 2017-01-21
LeetCode 153 - Find Minimum in Rotated Sorted Array

原题链接: 153. Find Minimum in Rotated Sorted Array


题干

有一个曾经升序排序的数组, rotate 了之后原先的起点在哪儿就不知道了。求最小值。

rotate 举例: 0 1 2 4 5 6 7 –> 4 5 6 7 0 1 2

思路

已排序,查找,先想到二分查找。

和正常二分查找的区别在哪儿?

Binary Search 时,搜索终止的条件是 a[mid] == target 或 lo > hi 。每次搜索都能确切知道下一次要搜索的区域(左边或右边)。

本题找到的条件是 a[mid] < a[mid - 1],返回 a[mid] 。没找到的条件是 lo > hi 。由于并不能确定断点发生在哪里,所以需要将两边都搜索。因为我检查的是前一个点,所以希望查到位置 0 时说明数组没有 rotate ,那就是说我递归时要先查后半部分,再查前半部分。如果直接用 mid = lo + (hi - lo) / 2 ,那在偶数时仍然会先查前半边,这个我的逻辑不和,所以使用 mid = lo + (hi - lo + 1) / 2 来确保及时偶数范围也会先查后半边的点。当两边都报告没有找到断点,那必然就是一个完全升序的数组了。

时间复杂度最差情况为 $O(N)$ ,在数组为完全升序时。

代码:

public int findMin(int[] nums) {
if (nums == null || nums.length < 2) {
return nums[0];
}
int pos = findMin(nums, 0, nums.length - 1);
// 没有找到断点
if (pos == -1) {
return nums[0];
}
return nums[pos];
}
private int findMin(int[] nums, int lo, int hi) {
// 区域内无断点
if (lo > hi) {
return -1;
}
int mid = lo + (hi - lo + 1) / 2;
// 知道最后也没有找到,数组内无断点
if (mid == 0) {
return -1;
}
if (nums[mid] < nums[mid - 1]) {
return mid;
}
// 找后半部分
int pos = findMin(nums, mid + 1, hi);
// 后半部分没找到,再找前半部分
if (pos == -1) {
pos = findMin(nums, lo, mid - 1);
}
return pos;
}