81. Search in Rotated Sorted Array II

same as 33, but data has duplicate numbers

just add this judgement, cant solve duplicate problems

// 多這個條件, 因為牽涉到 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)

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 比較一致

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