Intuition

문제에서 한번 회전된 배열이 input으로 들어오는 경우, 이진탐색을 적용할 수 없다.
즉, 회전되기 전의 배열을 구해야한다.

Approach

회전되기 이전의 배열을 구하기 위해 회전이 된 기준점인 pivot을 이진탐색을 통해 탐색했다.

우선, numsSize가 1인 경우의 pivot은 0일수밖에 없고, 회전이 되어있지 않은 케이스는 nums[l]<nums[r]로 판단할 수 있다.

int search(int* nums, int numsSize, int target) {
    int originalZeroIdx;
    int l=0;
    int r=numsSize-1;
    if (numsSize==1) originalZeroIdx=0;
    else{
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[l]<nums[r]){ 
                originalZeroIdx=l;
                break;
    ...
    }
...
}

가령, [6,7,8,9,1] 이라는 배열이 있다.
nums[l],nums[mid],nums[r]은 각각 6,8,1이 된다. nums[l]<nums[mid], nums[mid]>nums[r] 이므로 l부터 mid까지는 정렬이 되어있고 mid부터 r까지는 정렬이 되어있지 않은 즉, mid부터 r까지사이에 pivot이 있음을 알 수 있다.
그러므로 다음 번 탐색때는 r=mid로 두고 [8,9,1] 을 탐색한다. 한번 더 같은 과정을 반복하면 [9,1] 만 남게되고 l과 mid가 같아지게 된다.
이때 회전이 되지 않은 경우는 위에서 걸러졌으므로, 해당 배열은 무조건 회전이 한번 발생하였고 그 결과로 pivot이 항상 r에 위치하게 된다.

int search(int* nums, int numsSize, int target) {
    int originalZeroIdx;
    int l=0;
    int r=numsSize-1;

    if (numsSize==1) originalZeroIdx=0;
    else{
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[l]<nums[r]){ 
                originalZeroIdx=l;
                break;
            }
            if(nums[l]==nums[mid]){
                originalZeroIdx=r;
                break;
            }
            if(nums[l]>nums[mid]&&nums[mid]<nums[r]){ 
                r=mid;
            }
            else l=mid;
        }
    }
...
}

여기까지의 과정을 통해 pivot을 구했다.
[6,7,8,9,1]의 경우 pivot index는 4이다.이제 원래 배열을 구할 수 있고, 이진탐색도 가능해졌다.
가령, nums[0]에 접근했을 때 6이 아니라 나머지 연산을 통해, 회전시키기 전의 값인 1이 나오게만 만들어주면 된다.

Solution

int search(int* nums, int numsSize, int target) {
    int originalZeroIdx;
    int l=0;
    int r=numsSize-1;

    if (numsSize==1) originalZeroIdx=0;
    else{
        while(l<=r){
            int mid=l+(r-l)/2;
            if(nums[l]<nums[r]){ 
                originalZeroIdx=l;
                break;
            }
            if(nums[l]==nums[mid]){
                originalZeroIdx=r;
                break;
            }
            if(nums[l]>nums[mid]&&nums[mid]<nums[r]){ 
                r=mid;
            }
            else l=mid;
        }
    }

    l=0;
    r=numsSize-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        int idx=(mid+originalZeroIdx)%numsSize; // 회전시키기 전의 값을 구하는 나머지 연산
        if(nums[idx]==target) return idx;
        else if(nums[idx]>target) r=mid-1;
        else l=mid+1;
    }

    return -1;
}

교수님 풀이

우리는 정렬되어 있는 배열 내에서는 이진탐색을 활용할 수 있고, 또한 범위내에 target값이 존재하는지 여부에 대해서도 알 수 있다.

교수님의 풀이는 정렬되어있는 부분을 활용하여 이진탐색 알고리즘을 개선한다.

본 문제에서는 최대 한 번의 회전이 일어날 수 있기 때문에 배열을 반으로 나누면, 둘 중 하나는 무조건 정렬이 되어있을 수 밖에 없다.

가령 [6,7,8,9,1]에서 target이 6이라 할때, 배열은 [6,7,8] 과 [9,1]로 나뉜다.
nums[l]과 nums[mid]의 대소비교, nums[mid]와 nums[r]의 대소비교를 통해 각각의 정렬 여부를 알 수 있다.
정렬된 배열 [6,7,8]의 범위내에 target 6이 속하기 때문에 [6,7,8]과 [9,1] 중 전자에 대해 이진탐색을 계속한다. 만약 target이 9였다면 정렬된 배열[6,7,8]의 범위에 속하지 않기 때문에 후자를 택한다.

Solution

int search(int* nums, int numsSize, int target) {
    int ans=-1;
    int l=0;
    int r=numsSize-1;
    while (l<=r){
        int mid=l+(r-l)/2;

        if (nums[mid]==target){
            ans=mid;
            break;
        }
        else if (nums[l]<=nums[mid]){ // l부터 mid까지가 정렬된 배열인지 판단
            if (nums[l]<=target&&target<nums[mid]) r=mid-1; // 범위내에 속하는 경우
            else l=mid+1; // 범위내에 속하지 않는 경우
        }
        else {
            if (nums[mid]<target&&target<=nums[r]) l=mid+1;
            else r=mid-1;
        }
    }

    return ans;
}

Time Complexity

내 풀이와 교수님 풀이 모두 이진탐색만을 사용하므로 $O(log N)$이다.

지적 및 질문 환영