LeetCode 33번 - Search in Rotated Sorted Array

 

leetcode.com/problems/search-in-rotated-sorted-array/submissions/

Search in Rotated Sorted Array - LeetCode

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0;
        int r = nums.size()-1;
        
        while(l<=r){
            int mid = (l+r)/2;
            //target이 딱 중간에 있을경우
            if(nums[mid] == target) return mid;
            //target이 mid의 수보다 작을경우
            else if(nums[mid] > target){
                //일반적인 경우와 다를때: r의 값보다 mid의 값이 더 작고, target이 r의 값보다 작은거나 같은것에 속할때  
                if(nums[r]<nums[mid] && target <= nums[r]){
                   l = mid + 1; 
                }
                //target이 일반적으로 왼쪽에 있을경우
                else{
                    r = mid-1;
                }
            }
            //target이 mid의 수보다 클경우
            else{
                //일반적인 경우와 다를때: l의 값이 mid의 값보다 더 크고, target이 l보다 target이 큰거나 같은것에 속할때
                if(nums[l]>nums[mid] && target >= nums[l]){
                    r = mid-1;
                }
                //target이 일반적으로 오른쪽에 있을경우
                else{
                    l = mid+1;
                }
            }
        }
                
        return -1;
        
    }
};

 

이 문제의 포인트는 시간 조건을 맞추는 것이다. 

O(logN)이라는 조건을 맞추기 위해서는 for문 보다는 binary search를 이용하는것이 좋다. 

sorting이 되어있기 때문에 binary search를 사용할 수 있지만, 일반적인 binary search와는 조금 다르다. 

일반적으로는 무조건 큰건 오른쪽, 작은건 왼쪽에 가있지만, 

이 문제의 경우 큰것들이 작은쪽에 있을수도 있기 때문에 다른 조건을 하나 더 주어야 한다. 

위에 코드에 주석으로 잘 설명해 두었으니 참고하기를 바란다.