# 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?

## Analysis

``````while (start < end && nums[start] == nums[start + 1])start++;
while (start < end && nums[end] == nums[end - 1]) end--;
``````

## Solution

Template #3 (compare nums[mid] vs nums[right]) - (1 ms, faster than 56.43%)

``````class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}

int left = 0, right = nums.length - 1;

while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
return true;
}
if (nums[mid] < nums[right]) {
// right part is sorted, left part is rotated

if (target > nums[right] || target < nums[mid]) {
// target is in rotated part
right = mid;
} else {
left = mid;
}

} else if (nums[mid] > nums[right]) {
// left part is sorted, right part is rotated

if (target < nums[left] || target > nums[mid]) {
// target is in rotated part
left = mid;
} else {
right = mid;
}
} else {
right--;
}
}
if (nums[left] == target || nums[right] == target) {
return true;
}
return false;
}
}
``````

@hpplayer Template #1 (compare nums[mid] vs nums[left]) - ()

``````public boolean search(int[] nums, int target) {
int start  = 0, end = nums.length - 1;

//check each num so we will check start == end
//We always get a sorted part and a half part
//we can check sorted part to decide where to go next
while(start <= end){
int mid = start + (end - start)/2;
if(nums[mid] == target) return true;

//if left part is sorted
if(nums[start] < nums[mid]){
if(target < nums[start] || target > nums[mid]){
//target is in rotated part
start = mid + 1;
}else{
end = mid - 1;
}
}else if(nums[start] > nums[mid]){
//right part is rotated

//target is in rotated part
if(target < nums[mid] || target > nums[end]){
end = mid -1;
}else{
start = mid + 1;
}
}else{
//duplicates, we know nums[mid] != target, so nums[start] != target
//based on current information, we can only move left pointer to skip one cell
//thus in the worest case, we would have target: 2, and array like 11111111, then
//the running time would be O(n)
start ++;
}
}

return false;
}
``````

Template #1 with preprocessing of start, end

``````class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0)
return false;
int start = 0, end = nums.length - 1;
while (start <= end){
while (start < end && nums[start] == nums[start + 1])start++;
while (start < end && nums[end] == nums[end - 1]) end--;
int mid = start + (end - start) / 2;
if (nums[mid] == target)
return true;
if (nums[mid] < target){
if (nums[end] >= target || nums[start] < nums[mid])
start = mid + 1;
else
end = mid - 1;
}else{
if (nums[start] <= target || nums[end] >= nums[mid])
end = mid - 1;
else
start = mid + 1;
}
}
return false;
}
}
``````