[Binary Search][Medium] 153. Find Minimum in Rotated Sorted Array

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description

 

 

Q. 정렬된 배열이 회전 되어서 주어질 때, 이 배열 값 중 최소 값을 구하라. 

 

 

Solution. 

 Binary search 문제 중 단골이다. 

 풀이법을 반드시 알아야 하겠다. 

 

 정렬된 배열을 회전하면, 5가지 경우가 존재한다. 

 

 // 1, 2, 3, 4, 5

 // 5, 1, 2, 3, 4

 // 4, 5, 1, 2, 3, 

 // 3, 4, 5, 1, 2 

 // 2, 3, 4, 5, 1 

 

 최소값이 되는 지점을 left, mid, right로 놓고 전개하면 3가지 branch가 나온다. 

 // 1, 2, 3, 4, 5      - left

 // 5, 1, 2, 3, 4      - mid A 

 // 4, 5, 1, 2, 3,     - mid B

 // 3, 4, 5, 1, 2      - right A

 // 2, 3, 4, 5, 1      - right B

 

 이 중 mid A 와 right A 는 추가적인 전개가 해당 방향으로 필요하다. 

 위 로직으로 코드를 전개한다. 

 

    int findMid_BS(vector<int>& nums, int left, int right)
    {
        if (left > right) return -1;
        int mid = left + (right - left) / 2;

        // 1, 2, 3, 4, 5
        if (nums[left] <= nums[mid] && nums[mid] <= nums[right])
            return nums[left];
        
        // 4, 5, 1, 2, 3
        if (nums[left] >= nums[mid] && nums[right] >= nums[mid])
        {
            // 5, 1, 2, 3, 4 
            if (mid > 0 && nums[mid - 1] < nums[mid])
                return findMid_BS(nums, left, mid - 1);
            return nums[mid];
        }

        // 2, 3, 4, 5, 1
        if (nums[left] >= nums[right] && nums[mid] >= nums[right])
        {
            // 3, 4, 5, 1, 2
            if (right>0 && nums[right-1] < nums[right])
                return findMid_BS(nums, mid + 1, right);
            return nums[right];
        }
        return -1;
    }
public:
    int findMin(vector<int>& nums) 
    {
       return findMid_BS(nums, 0, nums.size() - 1);
    }

 

 

만족스러운 속도는 아니지만 어쨌든 TC는 만족할 것이다.