与33.搜索旋转排序数组不同的是,数组中的元素可以重复。
比如:数组【0 0 1 2 2 5 6】
经旋转变成【2 5 6 0 0 1 2】
解法一:顺序查找
略
解法二:二分查找
分析:
经过旋转后的数组,只是局部有序,整体并不有序,且有重复的元素,本题如何应用二分?
在开始的判断中,与33.搜索旋转排序数组题解原理相同,根据中间元素
mid
,将序列划分为[low,mid-1]
、mid
和[mid+1,high]
。
- 如果
target == nums[mid]
,代表找到了该元素,直接返回即可;- 否则,进行下面的处理。
在比较
target
和nums[mid]
之前,先比较nums[low]
和nums[mid]
的关系,原理如下:第一类序列:【2 3 3 4 6 1 2】,也就是
nums[low] < nums[mid]
,此例中为2<5。这种情况下,可以保证序列的前半部分是有序的。
- 如果
nums[low] <= target < nums[mid]
,则去前半部分找- 否则,去后半部分找
第二类序列:【6 1 2 2 3 3 4】,也就是
nums[low] > nums[mid]
,此例中为6>2。这种情况下,可以保证序列的后半部分是有序的。
- 如果
nums[mid] <= target < nums[end]
,则去后半部分找- 否则,去前半部分找
(至此,与33.搜索旋转排序数组题解解法一致)
第三类序列:【1 0 0 1 1 1 1】,这种情况下
nums[low] == nums[mid]
,这个时候无法判断是前半部分有序还是后半部分有序。无法判断的原因:
如序列【0 0 1 1 1 1 1】可以经过旋转变成上面的【1 0 0 1 1 1 1】,也可以旋转成【1 1 1 1 0 0 1】,这两种情况都是
nums[low] == nums[mid]
的如果根据【1 0 0 1 1 1 1】将这种序列判断成右序列有序,而0不在nums[3]nums[6],即11之间,就去左序列找,这样可能找到0。
但这样就会导致处理第二种序列【1 1 1 1 0 0 1】时,也认为右边有序,0不在1~1之间,就去左序列找,最后导致序列中有0,但返回false的结果。
(这也给我一个提醒,做算法题的时候,不要根据自己举的一个例子,或者根据题目中的一个例子去设计算法,而是根据一个适用性的规律来设计)
- 直接
low++
即可,相当于去掉一个重复的干扰项。
- 既然到了判断
nums[low]
和nums[mid]
的关系的环节,说明nums[mid]
不是要找的target,而nums[low] == nums[mid]
,所以nums[low]
也不是target,所以直接low++,不会影响查找的结果,而且可以去除重复的干扰项
代码:
bool rotateSearch2(vector<int>& nums, int target){
if(nums.size()==0) return -1;
int low=0,high=nums.size()-1;
while(low<=high){
int mid = low+(high-low)/2;
if(nums[mid]==target) return true;
else if(nums[low]<nums[mid]){
if(nums[low]<=target && target<nums[mid]){ //mid's left
high=mid-1;
}else { //mid's right
low=mid+1;
}
}else if(nums[low]>nums[mid]){
if(nums[mid]<target && target<=nums[high]){ //mid's right
low=mid+1;
}else { //mid's left
high = mid-1;
}
}else { //nums[low]==nums[mid]
//low与mid 重复,直接跳过重复项,在[low+1,high]中继续二分查找
low++;
}
}
return false;
}