Search in Rotated Sorted Array II:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public boolean search(int[] nums, int target) {
        if (nums.length == 0) return false;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;
            else if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            } else if (nums[mid] > nums[right]){
                if (nums[mid] > target && target >= nums[left]) right = mid - 1;
                else left = mid + 1;
            } else {
                right--;
            }
        }
        return false;
    }
}

Compare with:

Search in Rotated Sorted Array:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean search(int[] nums, int target) {
        if (nums.length == 0) return false;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;
            else if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            } else{
                if (nums[mid] > target && target >= nums[left]) right = mid - 1;
                else left = mid + 1;
            } 
        }
        return false;
    }
}

only the last else, right--/left++ to eliminate duplicates.

Reason: If we get here, it means nums[left] == nums[mid] == nums[right], then squeeze inside from both sides will not change the result but can help eroding duplicates from both sides. right-- or left++ would both do