# 63.Search in Rotated Sorted Array II

## 1.Description(Medium)

Follow up for [Search in Rotated Sorted Array](http://www.lintcode.com/problem/search-in-rotated-sorted-array/):

What if**duplicates**are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

**Example**

Given`[1, 1, 0, 1, 1, 1]`and target =`0`, return`true`.\
Given`[1, 1, 1, 1, 1, 1]`and target =`0`, return`false`.

## 2.Code

Solution 1: Binary Search

[ Search in Rotated Sorted Array 在旋转有序数组中搜索](http://www.cnblogs.com/grandyang/p/4325648.html)

的延伸，现在数组中允许出现重复数字，这个也会影响我们选择哪半边继续搜索，由于之前那道题不存在相同值，我们在比较中间值和最右值时就完全符合之前所说的规律：

**如果中间的数小于最右边的数，则右半段是有序的，若中间数大于最右边数，则左半段是有序的**。

而如果可以有重复值，就会出现来面两种情况，\[3 1 1] 和 \[1 1 3 1]，对于这两种情况中间值等于最右值时，目标值3既可以在左边又可以在右边，那怎么办么，对于这种情况其实处理非常简单，只要把最右值向左一位即可继续循环，如果还相同则继续移，直到移到不同值为止，然后其他部分还采用[Search in Rotated Sorted Array 在旋转有序数组中搜索](http://www.cnblogs.com/grandyang/p/4325648.html)中的方法

\[l,m]为递增序列的假设就不能成立了，比如如下数据\[1,3,1,1,1]

1. 对于每一个递增序列，遍历之，确认。
2. 找到pivot点，然后确定对应序列搜索。

如果A\[m]>=A\[l]不能确定递增，那就把它拆分成两个条件

1. A\[m]>A\[l] 递增
2. A\[m] ==A\[l] 确定不了，那就l++，往下看一步即可。

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

Solution 2: 遍历

```
// 这个问题在面试中不会让实现完整程序
```

```
// 只需要举出能够最坏情况的数据是 [1,1,1,1... 1] 里有一个0即可。
// 在这种情况下是无法使用二分法的，复杂度是O(n)
// 因此写个for循环最坏也是O(n)，那就写个for循环就好了
//  如果你觉得，不是每个情况都是最坏情况，你想用二分法解决不是最坏情况的情况，那你就写一个二分吧。
//  反正面试考的不是你在这个题上会不会用二分法。这个题的考点是你想不想得到最坏情况。
```

```
public boolean search(int[] A, int target) {
        for (int i = 0; i < A.length; i ++) {
            if (A[i] == target) {
                return true;
            }
        }
        return false;
    }
```


---

# 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://junnie.gitbook.io/nine-chapter/1.binary-search/63search-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.