Search in Rotated Sorted Array II

문제 자체는 전에 풀었던 Search in Rotated Sorted Array 랑 크게 다르지 않은데 시리즈로 되어 있는 문제는 이상하게 긴가민가 하게 다르게 내서 좀 어렵게 느껴지는 거같다.

전 시리즈랑 동일하게 pivot 을 찾은 다음에 target이 그 range 에 있으면 찾고 아니면은 범위를 옮기면 되는 문제다. 하지만 이 문제에서는 duplicate 가 허용이 되는 문제여서 좀 어렵게 느껴졌다.

3Sum 방식으로 내가 찾고자 하는 range 를 duplicate 지나면서 찾으면 되는 문제다. 이때는 while 문을 이용해서 duplicate 을 전부 다 제거해준다음에 내가 search 하고 싶은 범위만 찾을 수 있도록 해줬다.

일반적으로 unique 한 숫자일 경우 O(logn) 시간이 걸리지만 이렇게 duplicate 이 쭉 있을 경우 worst case O(n) 까지 갈 수 있다.

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1; 

        while(left < right){
            while(left < right && nums[left] == nums[left+1]) left++; 
            while(left < right && nums[right] == nums[right-1]) right--; 

            //cout << left << ' ' << right << endl; 

            int mid = (right + left) / 2; 

            if(nums[mid] > nums[right]){
                left = mid + 1; 
            } else{
                right = mid; 
            }
        }

        if(target > nums[nums.size()-1]){
            right = left; 
            left = 0; 
        } else{
            right = nums.size()-1; 
        }

        while(left <= right){
            int mid = (right + left) / 2; 

            if(nums[mid] == target) return true; 

            if(nums[mid] < target){
                left = mid + 1; 
            } else{
                right = mid -1; 
            }
        }

        //cout << left; 
        return false; 
    }
};