## 81. Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,`[0,0,1,2,2,5,6]`might become`[2,5,6,0,0,1,2]`).

You are given a target value to search. If found in the array return`true`, otherwise return`false`.

Example 1:

``````Input: nums = [2,5,6,0,0,1,2], target = 0

Output: true
``````

Example 2:

``````Input: nums = [2,5,6,0,0,1,2], target = 3

Output: false
``````

• This is a follow up problem to Search in Rotated Sorted Array, where `nums`may contain duplicates.
• Would this affect the run-time complexity? How and why?

Thoughts:

1. only change is to consider case where both num[i] == num[j] == num[mid]: (i.e [3,1,2,3,3,3]), we should both update i and j by 1.
2. Selecting the pivot: then compare the mid value with the pivot to decide which side is monotuous

Code: T:(O(n) ~ O(logn));

``````class Solution {
public:
bool search(vector<int>& nums, int target) {
int i = 0;
int j = nums.size()-1;
while(i <= j){
int mid = i + (j - i >> 1);
if (nums[mid] == target) return true;

if (nums[i] == nums[mid] && nums[j] == nums[mid]){i++; j--;}
else if (nums[i] == nums[mid] && nums[j] != nums[mid]) i = mid + 1;

else if(nums[i] < nums[mid]){
if(nums[i] <= target and nums[mid] > target){
j = mid - 1;
}
else{
i = mid + 1;
}
}

else if (nums[i] > nums[mid]){
if (nums[mid] < target and nums[j] >= target){
i = mid + 1;
}
else{
j = mid - 1;
}
}

else {
//
}
}

return false;
}
};
``````

Python: Pivot

``````class Solution(object):
def search(self, nums, target):
# the most annoying case is duplicate pivoting value in the array!!!
# [4,5,4,4,4,4,4]
# [4,4,4,4,4,5,4]
# when nums[mid] == pivot, it's impposible to decide whether you should move the
# lower bound or upper bound
if not nums: return False
pivot = nums
if target == pivot: return True

# !!key!!
# we move lo and hi so pivot will never equal to lo or hi
lo, hi = 0, len(nums) - 1
while hi >= 0 and nums[hi] == pivot:
hi -= 1
while lo <= len(nums) - 1 and nums[lo] == pivot:
lo += 1
# now we can just blindly copy the code from search-in-rotated-sorted-array-i
while lo <= hi:
mid = (hi - lo) // 2 + lo
if nums[mid] == target:
return True
if nums[mid] < pivot:
# mid is on the upper side
if nums[mid] < target < pivot:
lo = mid + 1
else:
hi = mid - 1
if nums[mid] > pivot:
if pivot < target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
return False
``````