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

# 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;
    }
```