题目详情可见 搜索旋转排序数组
遇到一道很有意思的题目,核心也是用二分搜索!关于二分搜索的技巧可见 二分搜索
本人一直在「收缩区间」处裹不清楚,直到看到了一句话就豁然开朗:旋转数组后,从中间划分,一定有一边是有序的
所以我们只需要判断哪边有序,然后判断是否在该有序区间内。如果不在,那么肯定在另一半区间内
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left - (left - right) / 2;
// 找到
if (nums[mid] == target) return mid;
// 左边有序
if (nums[left] <= nums[mid]) {
// target 在左边
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
} else {
// target 在右边
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return -1;
}
注意:if (nums[left] <= nums[mid])
一定需要包含=
;如果没有包含,左区间收缩会出现错误
例如样例:nums = {3, 1}, target = 1
题目详情可见 寻找旋转排序数组中的最小值、寻找旋转排序数组中的最小值 II、剑指 Offer 11. 旋转数组的最小数字
上述三个题目基本上一模一样,所以放在一起
用l, r
分别表示左右边界指针,mid = l - (l - r) / 2
如果nums[mid] > nums[r]
,则最小值一定落在区间[mid + 1, r]
中,如下图所示:
如果nums[mid] < nums[r]
,则最小值一定落在区间[l, mid]
中,如下图所示:
注意:此时是mid
,而不是mid - 1
,因为最小值可能在mid
处取得,如下图所示:
如果nums[mid] = nums[r]
,则最小值一定落在区间[l, mid]
,但是问题在于应该如何收缩区间呢?答案为:r = r - 1
由于可能存在重复的元素,对于下图所示的情况,r = r - 1
为无错过收缩,即最小值依然在[l, r - 1]
中
如果r
恰好就是最小值,那么r = r - 1
后就刚好错过了最小值,即最小值不在[l, r - 1]
中,如下图所示:
但是区间[l, r - 1]
为单调递增,所以最终一定会收缩到区间[l, l - 1]
时结束,即区间[0, -1]
由于nums[mid] = nums[r]
,所以nums[l ... mid]
一定都和nums[r]
相等
下面给出详细代码:
xxxxxxxxxx
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left - (left - right) / 2;
if (nums[mid] > nums[right]) left = mid + 1;
else if (nums[mid] < nums[right]) right = mid;
else right -= 1;
}
return nums[left];
}