# 81. Search in Rotated Sorted Array II

[https://leetcode.com/problems/search-in-rotated-sorted-array-ii/](https://leetcode.com/problems/search-in-rotated-sorted-array-ii/)

## solution

* 存在重复值
* 返回的值是否存在

```python
class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        if not nums:
            return False

        l = 0
        r = len(nums) - 1

        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] == target:
                return True

            if nums[mid] == nums[l]: # Fail to estimate which side is sorted, if的这一环节一开始没想到
                l += 1  # In worst case here: O(n)

            elif nums[mid] > nums[l]:
                if nums[mid] > target >= nums[l]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[r]:
                    l = mid + 1
                else:
                    r = mid - 1
        return False
```

时间复杂度：O(n)\
空间复杂度：O(1)
