> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/array/81search-in-rotated-sorted-array-ii.md).

# 81\_Search in Rotated Sorted Array II

## 81. Search in Rotated Sorted Array II

Level: medium

Tag: array, binary search

## Question

### follow up of Q33 Search in Rotated Sorted Array

**What if duplicates are allowed? Would this affect the run-time complexity? How and why?**

```
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Write a function to determine if a given target is in the array.
The array may contain duplicates.
```

### Example 1

```
Input: nums = [1, 2, 1, 1, 1]
       target = 2
Output: Ture
```

### Idea (binary search)

Use the algorithm for Q33. Add one more test to avoid conner cases like example 1. Bad thing about example 1 is that when middle point is third integer, either half is sorted. We can further **check if middle integer is the same as left and right**. If yes, move left and right one step further.

### Complexity

* Time:$$O(logn)$$ 
* Space:$$O(1)$$

### Solution

```python
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        # pay attention: return is boolean not index

        left, right = 0, len(nums)-1

        while left <= right:
            mid = (left + right)//2
            if nums[mid] == target:
                return True

            # new tricky part (comparing with Q33 search in rotated sorted array)
            if nums[left] == nums[mid] == nums[right]:
                left += 1
                right -= 1
            # end of new tricky part

            elif nums[left] <= nums[mid]:
                # left half must be sorted
                # test if target is in left half
                if nums[left] <= target < nums[mid]:
                    # keep left half
                    right = mid - 1
                else:
                    # keep right half
                    left = mid + 1
            else:
                # right half must be sorted
                # test if target is in right half
                if nums[mid] < target <= nums[right]:
                    # keep right half
                    left = mid + 1
                else:
                    # keep left half
                    right = mid - 1
        return False
```