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

# 81. Search in Rotated Sorted Array II

same as 33, but data has duplicate numbers

just add this judgement, cant solve duplicate problems

```java
// 多這個條件, 因為牽涉到 start, end , 所以都要處理
            if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
                start++;
                end--;
            } 
            
            
            // 其實只寫這樣也可以
            if (nums[mid] == nums[end]) {
                end--;
            }
```

time: O(logn)

space: O(1)

```java
class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        
        while (start <= end) {
            int mid = (start + end) >> 1;
            if (nums[mid] == target) return true;
            
            
            // 多這個條件
            if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
                start++;
                end--;
            } else if (nums[start] <= nums[mid]) {
                if (nums[start] <= target && target <= nums[mid]) { // in left
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
                    
            } else {
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            
        }
        return false;
    }
}
```

## 我想這個寫法跟 154 比較一致

```java
class Solution {
    public boolean search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        
        while (start <= end) {
            int mid = (start + end) >> 1;
            if (nums[mid] == target) return true;
            
            
            if (nums[start] < nums[mid]) {
                if (nums[start] <= target && target <= nums[mid]) { // in left
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
                    
            } else if (nums[start] > nums[mid]) {
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            } else {
                start++;
            }
            
        }
        return false;
    }
}
```