# 081. Search-in-Rotated-Sorted-Array-II

difficulty: Medium

&#x20;section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }&#x20;

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](https://github.com/yangzichao/Leetcode/tree/368454cedd065d73e093d3d6237ede93a9c8a605/problems/search-in-rotated-sorted-array/description/README.md), where `nums` may contain duplicates.
* Would this affect the run-time complexity? How and why?

## Method One

```java
public class Solution {
​
    public boolean search(int[] nums, int target) {
        /**
        因为有 duplicates, 所以 worst case O(N);
        */
        int left = 0;
        int right = nums.length - 1;
        while( left <= right ) {
            int pivot = left + (right - left)/2;
            if (nums[ pivot ] == target) {
                return true;
            }
            //If we know for sure right side is sorted or left side is unsorted
            if (nums[pivot] < nums[right] || nums[pivot] < nums[left]) {
                if (target > nums[ pivot ] && target <= nums[ right ]) {
                    left = pivot + 1;
                } else {
                    right = pivot - 1;
                }
            //If we know for sure left side is sorted or right side is unsorted
            } else if (nums[ pivot ] > nums[ left ] || nums[ pivot ] > nums[right]) {
                if (target < nums[ pivot ] && target >= nums[ left ]) {
                    right = pivot - 1;
                } else {
                    left = pivot + 1;
                }
            //If we get here, that means nums[ left ] == nums[ pivot ] == nums[ right ], then shifting out
            //any of the two sides won't change the result but can help remove duplicate from
            //consideration, here we just use end-- but left++ works too
            } else {
                right--;
            }
        }

        return false;
    }
}
​
​

​
```
