```
class Solution {
public:
bool search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
/// Skip the duplicates on two boundaries.
while (left < right && nums[left] == nums[right]) ++left;
while (left < right && nums[right] == nums[right - 1]) --right;
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
/// If the lower half is in order.
if (nums[left] <= nums[mid]) {
/// If target is within the lower search range.
if (nums[left] <= target && target < nums[mid]) right = mid - 1;
else left = mid + 1;
/// If the upper halp is in order.
} else {
/// If target is within the upper search range.
if (nums[mid] < target && target <= nums[right]) left = mid + 1;
else right = mid - 1;
}
}
return false;
}
};
```

Time complexity: In worst case is O(n)