题目描述故意用了一些难懂的词汇,什么pivot index、rotate。仔细推一推样例就能明白,其实就是把一个递增数列划分为[0, k-1]、[k, n-1]两个子数列。并将[k, n-1]放到[0, k-1]前面。input给出的是这个已经操作完了的数列,让我们在里面找到指定元素target的位置,没有就返回-1。要求算法必须是O(logn)级别。几个决定边界的条件:
1.所有元素各不相同。(不需要考虑左右边界相等的情况)
2.nums is an ascending array that is possibly rotated.(意味着可能它没有旋转过,是一个递增数列!!这个很坑!需要在第一次用二分找完k之后看下k是不是-1)
二分
O(logn),基本可以确定是要用二分来做。但这个数列并不是单调的,怎么去找target呢?整个数列不单调,但是两个子数列单调,所以只要找到正确划分子数列的方法分别二分就可以了。 对于位置为k的元素: 普通的二分,因为数列是单调的,所以只要判断mid是比target_value大还是小,就能判断出是要动左端点还是右端点。虽然本题不单调,不能直接这么做,但核心思想是一样的,即左右端点的移动是通过对mid和某个值的比较来决定的。 不相等之后,就要移动左右端点了。如果mid比target_value大,下面是最常见的做法。 但是,这实际上是一种简化!本质的判断是这样的: 如果不符合,再来看另一个子区间。 但其实上面的很多条件都是可以简化的,比如[left, right]作为起始区间,其实没必要再判断nums[right] nums[left]是否符合target_value的大小条件了,加上二者是互斥的,target_value不在第一个区间它就一定在第二个区间,所以直接用else就可以。这样才有了常见的形式: 3.2中常见二分的条件是基于递增数列的性质推断出的,本题的条件是什么呢?其实这个条件和3.1里对mid判断的条件是一样的。 实际写进去就是这样: 但是!这里还有一个特殊情况,以这个test case为例子: 为什么我们不特判mid==nums.size()-1的情况呢?因为k它不可能出现在最后的,如果它后面没有元素,那不可能完成旋转,它前面也不会有,这种只有一个元素的情况我们已经在开头特判排除了。 Time complexity: O(logn)
那么在找分界点k的时候,如何判断每一轮left、right的变化条件呢?关键在于原本的数列是一个递增数列,所以[k, n-1]里所有的元素都大于[0, k-1]。也就是说,nums[n-1]>nums[0]。给定数列里的所有元素都满足nums[n-1]3.1对mid的判断
nums[n]
对于位置为k-1的元素:
nums[n]>nums[n-1] && nums[n]>nums[n+1] && nums[n-1]>nums[n+1]
找k或者k-1都可以,本质都是为了找到两个子数列的分界点。
上面列出来的k和k-1的条件,就是我们二分查找里判断mid的条件,如果符合就break,不符合就改变区间的左或者右端点继续找。3.2区间左右端点移动的判断
单调序列中,mid和target比,是为了确定mid的位置是在前半段还是后半段,只是这两段长度均等。而我们在本题中,target_value是两个子数列的分界点,两个子数列不均分,所以我们也需要判断mid的位置。但我们判断的是它在靠前的第一个子数列还是第二个子数列。本质上,这都是一种对子区间的判断。只不过普通二分因为单调的性质,判断起来容易了许多而已!
判断一个点在哪个子区间,核心就是判断点和区间左右端点的关系!
传统的二分看起来是直接和target_value对比了,但这只是因为它利用了单调区间的特性做了简化!它最原始的样子应该也是和端点做比较。
比如这一轮我们有left, right, mid。首先比较一下mid和target_value是否相等。if(nums[mid] == target_value) break;
if(nums[mid] > target_value)
right = mid-1;
因为是二分,移动方式是特定的(每次减半),不需要像双指针那样千变万化。所以每一轮我们做的事情就是去搞清楚,下一轮是选择[left, mid-1]这个区间,还是[mid+1, right]。
已知因为单调递增的特性,target_value所在的区间,一定满足nums[left] < target_value < nums[right]。(下面if里写的是闭,主要是因为随着寻找,区间最后会缩成只有2个元素或者只有1个元素。)
所以我们实际思考的是://先判断下[left, mid-1]这个子区间
if (nums[left]<=target_value && target_value<=nums[mid-1])
right = mid-1; //这个不是因为什么模板-1,不是为了什么循环结束-1,而是上面分析的,因为我们选择了这个子区间!而它的端点是mid-1!
if (nums[right]>=target_value && nums[mid+1]<=target_value)
left = mid+1; //同上,是因为我们选了第二个子区间,而它的端点是mid+1
else
left = mid+1;
3.3本题中的应用
因为找这个分界点的过程,它一定是从区间对半减少直至左右重合只剩一个点。mid的相邻元素的条件,就是区间的条件。因为它的左右元素就是它所在的最小区间。
它的原理是很好理解的,如果当前的区间是左端点大于右端点的,那它一定是两个数列都横跨了,我们要找的界限一定在这里。而如果当前区间是左端点小于右端点
里我选择找位置为k的元素,所以每一轮我们选择子区间的原则就是在[left, mid-1]与[mid+1, right]里选择满足nums[left]>nums[right]的那一个。if(nums[left]>nums[mid])
right = mid-1;
else if(nums[mid]>nums[right])
left = mid+1;
if(nums[mid-1]>nums[mid+1]) break;
if(nums[left] > nums[mid-1])
right = mid-1;
else if(nums[mid+1] > nums[right])
left = mid+1;
else{
mid = -1;
break;
}
[5,1,2,3,4]
对这种k出现在最开始的情况,它没有左边的相邻元素,如果不做特别处理就会越界。所以在最前面加一句特判:if(mid==0 && nums[mid]>nums[mid+1]) break;
4.代码
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size()-1, mid, ans = -1, pivot;
if(nums.size() < 3){
for(int i = 0;i < nums.size();i++){
if(nums[i] == target)
ans = i;
}
return ans;
}
//find the pivot index k
while(left <= right){
mid = left + (right-left)/2;
if(mid==0 && nums[mid]>nums[mid+1]) break;
if(nums[mid-1]>nums[mid+1]) break;
if(nums[left] > nums[mid-1])
right = mid-1;
else if(nums[mid+1] > nums[right])
left = mid+1;
else{
mid = -1;
break;
}
}
if(mid == -1)
pivot = nums.size();
else if(mid&&nums[mid-1]>nums[mid])
pivot = mid;
else
pivot = mid+1;
//search the 1st sequence using binary search
left = 0, right = pivot-1;
while(left <= right){
mid = left + (right-left)/2;
if(nums[mid] == target){
ans = mid;
break;
}
if(nums[mid] > target)
right = mid-1;
else
left = mid+1;
}
//search the 2nd sequence
left = pivot, right = nums.size()-1;
while(left <= right){
mid = left + (right-left)/2;
if(nums[mid] == target){
ans = mid;
break;
}
if(nums[mid] > target)
right = mid-1;
else
left = mid+1;
}
return ans;
}
};
5.复杂度
Space complexity: O(1)