[LeetCode] 33. Search in Rotated Sorted Array

문제링크

정렬이 된 상태에서 회전된 Array가 주어졌을 때, 주어진 target의 위치를 O(log n)의 시간복잡도로 구해야 하는 문제이다. O(log n)이기 때문에 binary search로 해결해야 하는데, 조건을 어떻게 줄 것인지를 생각하느라 많이 애먹었었다.

array의 맨 앞의 인덱스를 l, 맨 뒤의 인덱스를 r이라고 했을 때,

• array[l]이 array[r]보다 작다면 -> array는 제대로 정렬이 되어있는 상태
• array[l]이 array[r]보다 크다면 -> array는 회전이 되어있는 상태

위의 경우에는 바로 binary search를 적용하면 되지만, 아래의 경우에는 조금 더 생각해주어야 한다.

array에서 가운데를 기준으로 왼쪽 혹은 오른쪽 둘 중 하나는 제대로 정렬이 되어 있다는 가정에서 출발한다.

왼쪽이 정렬되어 있는 경우(arr[l] < arr[mid])

• target이 arr[l]보다는 크고, arr[mid]보다 작다면 왼쪽 array에서 target을 찾는다.
• 그렇지 않다면, 오른쪽 array에서 target을 찾는다.

오른쪽이 정렬되어 있는 경우(arr[mid] <= arr[r])

• target이 arr[mid]보다는 크고, arr[r]보다 작다면 오른쪽 array에서 target을 찾는다.
• 그렇지 않다면, 왼쪽 array에서 target을 찾는다.

이를 코드로 작성하면 아래와 같다.

int binary_search(int arr[], int l, int r, int target) {
    
    while(l<=r)
    {
        int mid = l+(r-l)/2;
        if(arr[mid]==target) return mid;
        if(arr[l]<=arr[mid]){
            if(arr[l]<=target && target<arr[mid]) r=mid-1;
            else l=mid+1;
        }
        else {
            if(arr[mid]<target && target<=arr[r]) l=mid+1;
            else r=mid-1;
        } 
    }


    return -1;
}

int search(int* nums, int numsSize, int target){
    return binary_search(nums, 0, numsSize-1, target);
    
}