---
description: '# Medium'
---

# 81. Search in Rotated Sorted Array II

### Solution 1:

1. Keep one of them when having repeated elements at the beginning and end of the list
2. Look for the pivot, which is to find the first pivot position. _(In order to deal with two situations on time: it's an ascending list, it's a rotated list, always compare `mid` and `left` first which means keep the left side is an ascending list.)_
3. Do binary search according to above two situations
4. Consider the edge case: 0 element

{% hint style="danger" %}
\[6,8,5,5,5] and \[6,8,9,9,9]

\[5,5,5,4]  and \[4,5,5,5]

When looking for the pivot, if value(mid) = value(left), keep right side
{% endhint %}

```python
while left + 1 < right:
    mid = left + (right - left)//2
    if nums[mid] >= nums[left]:
        left = mid
    else:
        right = mid
pivot = right
```

{% hint style="success" %}
Judging the list is an ascending or rotated list according to comparison of `nums[left]` and `nums[right]`, then do binary search at the same time
{% endhint %}

Time complexity: Because we can't confirm time complexity of step1. The worst case is $$T=O(n)$$ . Except that step, time complexisty = $$O(lgN)$$&#x20;

### Solution 2:

1. remove the repeated elements from start and end
2. find the pivot, consider three cases
3. search the target, consider three cases

```python
// Python
class Solution:
    def search(self, nums: List[int], target: int) -> bool: 
        # remove the some elements of begining and end
        start = 0
        for i in range(len(nums)-1):
            if nums[i] != nums[i+1]:
                break
            else:
                start = start + 1
                
        end = len(nums) - 1
        for i in reversed(range(1, len(nums))):
            if nums[i] != nums[i-1]:
                break
            else:
                end = end - 1
                
        if start >= end:   # [0, 0, 0, 0]
            if target == nums[start]:
                return True
            else:
                return False
                
        # find the pivot
        left = start
        right = end
        while left < right:
            mid = left + (right - left) // 2
            if nums[mid] ==  nums[right]:
                right = mid
            elif nums[mid] < nums[right]:
                right = mid
            else:
                left = mid + 1
        
        # search the target
        pivot = left
        if target >= nums[pivot] and target <= nums[end]:
            start = pivot
        else:
            end = pivot
        
        while start <= end:
            mid = start + (end - start) // 2
            if nums[mid] == target:
                return True
            if nums[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
                
        return False
```

### Solutioin 3 (Java one-pass):

1. remove same element from end, such as \[4, 4, 5, 1, 3, 4, 4] -> \[4, 4, 5, 1, 3]
2. Same as #33, two cases: \[start, end] is rotated; \[start, end] is not rotated

```java
// java efficient one-pass
class Solution {
    public boolean search(int[] nums, int target) {
        // remove same element from end
        int end = nums.length - 1;
        // at least keep one element
        while(end > 0) {
            if(nums[end] != nums[0])
                break;
            end --;
        }
        
        int start = 0;
        while(start <= end) {
            int mid = start + (end - start)/2;
            if(nums[mid] == target)
                return true;
            // [start, end] not rotated
            else if(nums[mid] >= nums[start]) {
                if(target < nums[mid] && target >= nums[start])
                    end = mid - 1;
                else
                    start = mid + 1;                
            }
            // [start, end] is rotated
            else {
                if(target > nums[mid] && target <= nums[end])
                    start = mid + 1;
                else
                    end = mid - 1;
            }
        }
        
        return false;
    }
}java
```
