# 81. Search in Rotated Sorted Array II

## problem description

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://leetcode.com/problems/search-in-rotated-sorted-array/description/), where `nums` may contain duplicates.
* Would this affect the run-time complexity? How and why?

## algorithm thought

相比于[Search in Rotated Sorted Array](https://kongchengzhuge.gitbook.io/leetcode/33.-search-in-rotated-sorted-array)，这题在数组中加入了重复的数字，导致会出现一些问题。比如left和right是一样的数，甚至是，left和mid和right都是一样的数，这就不好区分两个区间。首先使用一个循环处理，如果left和right一样，将left++。这样就能去除所有边界一样的情况。除去之后，就和前面没有重复数组是一样的处理情况了

## code

```cpp
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            while(left<right&&nums[right]==nums[left])
                left++;
            int mid=left+(right-left)/2;
            if(nums[mid]==target)
                return true;
            if(nums[mid]<=nums[right]){
                if(target>nums[mid]&&target<=nums[right]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }else{
                if(target>=nums[left]&&target<nums[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }
        }
        return false;
    }
};
```

## algorithm analysis

本来是二分查找的变体，时间复杂度应该是O(lgn)，但是这里有个对left和right的预处理，最坏情况下，时间复杂度会到O(n)。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kongchengzhuge.gitbook.io/leetcode/81.-search-in-rotated-sorted-array-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.