题目描述
Follow up for "Search in Rotated Sorted Array":What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7
might become 4 5 6 7 0 1 2
).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
和之前的旋转数组相比，如果增加重复元素这一限制，最终算法会有什么影响？如果旋转数组里有指定的元素，则返回true，否则返回false
代码及注释
class Solution {
public:
int search(vector<int>& nums, int target) {
// 线性表搜索问题一般都会用到二分法
// 二分法涉及三个指针min max mid
int min = 0, max = nums.size()-1;
// 二分法最终的停止条件
while(min <= max){
// 初始第一次二分的mid
int mid = (min+max)/2;
// 如果mid恰好是target(最终target都会到mid这里)
if(nums[mid] == target) return true;
// 如果左半部分有序,则在此半部分（有序字符串）进行二分查找
if(nums[min] < nums[mid]){
if(nums[min]<=target && target<nums[mid])
max = mid - 1;
else
min = mid + 1;
}else if(nums[min] > nums[mid]){
if(nums[mid]< target && target<=nums[max])
min = mid + 1;
else
max = mid - 1;
}else{
min++;
}
}
// 不满足最高二分条件min<max时
return false;
}
};
分析
由于重复元素的存在，上一题判断是否有序（递增）的方式：nums[min] <= nums[mid] 不再成立。那么可以把之前的两部分判断分成三部分：
- nums[min]<nums[mid]：则[min,mid]递增；
- nums[min]=nums[mid]：跳过，min++
