题目描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组[0,1,2,4,5,6,7]
可能变为[4,5,6,7,0,1,2]
)。
搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回-1
。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是$O(\log n)$ 级别。
样例1
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
样例2
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
算法1
(两次二分) $O(\log n)$
借用一下y总的图:
比较自然的想法是先利用二分找到旋转点(即最小值点),然后判断答案在哪一段内,之后在有序的两段内再二分搜索答案。
C++ 代码
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
int l = 0, r = nums.size() - 1;
if (nums[0] > nums.back()) { //如果是翻转的,找到最小值的位置
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] < nums[r]) r = mid;
else l = mid + 1;
}
if (target >= nums[0]) r = l - 1, l = 0;//确定目标值在前一半区间
else l = l, r = nums.size() - 1;//后一半区间
}
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
if (nums[l] == target) return l;
return -1;
}
};
算法2
(一次二分) $O(\log n)$
其实二分并不一定局限在有序区间内,只要区间具有二段性就可以二分,即区间具有某个性质可以将区间分为两段,使得每次搜索时都能将区间缩小而且保证答案仍在区间内。
观察上面的示意图可以注意到根据中点nums[mid]
与右边界nums[r]
的关系我们可以知道中点mid
处于哪一段上,如果处于左半段上那么区间可以分成[l, mid]
以及[mid + 1, r]
,我们判断一下答案在哪一个区间内就可以更新边界了,这里为了方便选了左半区间来判断。如果处于右半段上那么区间同样可以分成[l, mid]
以及[mid + 1, r]
,这里为了方便可以取右半区间来判断。
以上分析对于数组没被旋转过的情况也适用,相当于中点一直处于左半段上。
C++ 代码
class Solution {
public:
int search(vector<int>& nums, int target) {
if (nums.empty()) return -1;
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] <= nums[r]) {
if (target > nums[mid] && target <= nums[r]) l = mid + 1;
else r = mid;
} else if (nums[mid] > nums[r]) {
if (target <= nums[mid] && target >= nums[l]) r = mid;
else l = mid + 1;
}
}
return nums[l] == target ? l : -1;
}
};
这个题目是Y总在哪个专题讲解的啊?? 谢谢
2019LeetCode暑期打卡活动-Week 1,b站有录播。
好的 谢谢~~
81题就用的int t = nums.size() - 1,if (nums[mid] <= nums[t]) r = mid;
恩,这里数组元素都是不同的,我们在二分的时候始终保证了答案在
[l, r]
这个区间里,虽然右边界r
会被不断更新,但是显然最小值是一直满足小于nums[r]
的,所以这里写成小于nums.back()
或者nums[r]
都是可以的,nums.back()
会更直观些。第6行,nums[mid] < nums[r],这里r会更新,可能一般就取的nums[0]或nums[n]这样
嗯,我看旋转最小值取的固定值,是不是取nums[r]也可以
什么意思,能说的具体一点吗,在哪一行?
有可能没旋转,nums[nums.size()-1] 就是最大值了
两次二分那里找最小值应该是nums[mid] < nums[n]
你是想说
nums[mid] < nums[r]
吗?