LeetCode 81 Search in Rotated Sorted Array II [binary search] <c++>
给出排序好的一维有重复元素的数组,随机取一个位置断开,把前半部分接到后半部分后面,得到一个新数组,在新数组中查找给定数是否存在,时间复杂度限制\(O(log_2n)\)
C++
因为有重复元素存在,nums[l] <= nums[mid]
不能说明[l,mid]
区间内一定是单调的,比如数组[1,2,3,1,1,1,1]
,但是严格小于和严格大于的情况还是可以判断的。所以当nums[l] == nums[mid]
时,令l++
,跳过这个重复元素。所以其实该算法最坏情况下(所有元素相同)时间复杂度是\(O(n)\)的。
class Solution {
public:
bool search(std::vector<int>& nums, int target) {
int l = 0,r = nums.size();
while (l<r){
const int mid = l + (r-l)/2;
if(nums[mid] == target) return true;
if(nums[l] < nums[mid]) // [l,mid]区间单调不降
if(nums[l] <= target && target < nums[mid]) r = mid; // target 在区间内
else l = mid + 1; // target 不在区间内
else if(nums[mid] < nums[l]) // [mid,r]区间单调不降
if(nums[mid] < target && target <= nums[r-1]) l = mid + 1; // target 在区间内
else r = mid; // target 不在区间内
else l++; //跳过这个重复元素
}
return false;
}
};