# 81. Search in Rotated Sorted Array II
## Level - Medium
## Question
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
Follow up:
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?
### Thought 1 - Two pointers
This problem is the same type of [33. Search in Rotated Sorted Array.](/DoR6t8e3TXyOcy-ZiQLntg) But we can skip those duplicate numbers.
Runtime: 60 ms
#### Implementation
```python=
class Solution:
def search(self, nums: List[int], target: int) -> bool:
p1 = 0
p2 = len(nums)-1
while p1 <= p2:
if nums[p1] == target:
return True
else:
n = nums[p1]
p1 += 1
while p1 < p2 and n == nums[p1]:
p1 += 1
if nums[p2] == target:
return True
else:
n = nums[p2]
p2 -= 1
while p1 <= p2 and n == nums[p2]:
p2 -= 1
return False
```
#### Implementation
```C++=
```
### Thought 2 - Binary Search
I believe binary search is the reason why LeetCode rate it as Medium level. But this way is not faster than two pointers... Anyway, let's explain how to implementate it.
Due to the pivot, the list is divided as two list. But we cannot know where the pivot is. So we need to compare target value to (1)mid value (2)right value. There're 2 situations as below:
1. mid value is larger than right value.
```
Example: arr = [2, 3, 4, 5, 0 ,1]
```
arr[mid] is 5 and larger than arr[right]. Then choosing to go left or right depends on target value.
* (1-1) If target is larger than arr[right] and is smaller than arr[mid], it goes to search from left postion to the left side of mid postion.
* (1-2) Else it goes to search from the right side of mid to the right postion.
```
Diagram (1-1)
[2, 3, 4, 5, 0, 1] => [2, 3, 4, 5, 0, 1]
tar mid rig tar rig
---------------------------------------------------------------
Diagram (1-2)
[2, 3, 4, 5, 0, 1] => [2, 3, 4, 5, 0, 1]
mid tar rig mid lef rig
```
2. mid value is smaller than right value.
```
Example: arr = [3, 4, 5, 0 ,1, 2]
```
arr[mid] is 5 and smaller than arr[right]. Then choosing to go left or right depends on target value.
* (2-1) If target is smaller than arr[right] and is larger than arr[mid], it goes to search from the right side of mid to the right postion.
* (2-2) Else it goes to search the left side of mid postion.
```
Diagram (2-1)
[3, 4, 5, 0 ,1, 2] => [3, 4, 5, 0 ,1, 2]
lef mid tar rig lef rig
---------------------------------------------------------------
Diagram (1-2)
[3, 4, 5, 0 ,1, 2] => [3, 4, 5, 0 ,1, 2]
lef tar mid rig lef tar rig
```
Runtime: 60 ms
#### Implementation
```python=
class Solution:
def search(self, nums: List[int], target: int) -> bool:
left, right = 0, len(nums)-1
mid = left + (right-left) // 2
while left <= right:
mid = left + (right-left) // 2
if nums[mid] == target:
return True
if nums[mid] < nums[right]:
if target >= nums[mid] and target <= nums[right] :
left = mid + 1
else:
right = mid - 1
elif nums[mid] > nums[right]:
if target >= nums[left] and target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
# For duplicate
if nums[left] == target or nums[right] == target:
return True
left += 1
right -= 1
return False
```
#### Implementation
```C++=
```
### Thought 3 -
#### Implementation
```python=
```
#### Implementation
```C++=
```
Google Drive
Gist
Clipboard
Sign in with Wallet
