LeetCode 33. Search in Rotated Sorted Array

Search in Rotated Sorted Array - LeetCode

 

문제 설명

nums배열은 원래 오름차순으로 정렬된 배열에서 왼쪽으로 k번 회전한 배열이다

예를 들러 nums가 [4,5,6,7,0,1,2] 로 주어지면

원래 배열인 [0,1,2,4,5,6,7]에서 왼쪽으로 3번 회전 한 것이 무넺에서 주어진 nums배열이라는 것.

그리고 이 배열에서 target의 인덱스를 찾아 반환하는 문제. 만일 이 target이 nums배열에 없다면 -1을 반환

이 target을 찾을때의 시간 복잡도는 O(log n)에 찾아야함

 

입력: nums = [4,5,6,7,0,1,2], target = 0
출력: 4

 

문제 풀이

문제에서 중요한 것은 이 회전된 배열에서도 어떤 피봇을 중심으로 보면 왼쪽 혹은 오른쪽은 항상 정렬이 되어있다는 것임.

따라서 이 피봇을 중심으로 좌 우 구간을 판단 하고 이 target이 그 구간에 존재 한느지 판단하면서 탐색 범위를 줄여가는 이분 탐색을 이용하여 문제를 풀었음

 

간단한 정리

1. mid기준으로 target이 좌 우 범위 중 어디 범위에 있는지 확인

2. 만약에 좌 우 범위 중 target이 있으면 target이 있는 범위를 탐색 

3. 만일 없다면 반대 쪽으로 탐색함

4. 탐색이 완료 되었다면 탐색 범위를 절반으로 감소 시켜서 다시 mid를 갱신한 후에 target을 찾음

 

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int arrSize = nums.size();

        int left = 0;
        int right = arrSize - 1;

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

            // target을 찾은 경우
            if(nums[mid] == target)
            {
                return mid;
            }

            // mid 기준 오른쪽 구간이 정렬되어 있는 경우
            else if(nums[mid] < nums[right])
            {
                // target이 정렬된 오른쪽 구간에 있다면 오른쪽 탐색
                if(nums[mid] < target && target <= nums[right])
                {
                    left = mid + 1;
                }
                // 그렇지 않으면 왼쪽 탐색
                else
                {
                    right = mid - 1;
                }
            }

            // mid 기준 왼쪽 구간이 정렬되어 있는 경우
            else
            {
                // target이 정렬된 왼쪽 구간에 있다면 왼쪽 탐색
                if(nums[left] <= target && target < nums[mid])
                {
                    right = mid - 1;
                }
                // 그렇지 않으면 오른쪽 탐색
                else
                {
                    left = mid + 1;
                }
            }
        }

        // target을 찾지 못한 경우
        return -1;
    }
};

 

 

글 내용 중에 틀린 것이 있거나 궁금한 것이 있다면 댓글 남겨주세요! 봐주셔서 감사합니다.