[BinarySeach][Medium] 153. Find Minumum in Rotated Sorted Array

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

 

주어진 정렬된 배열이 rotated 되어 있을 때, 최소 값 원소를 찾아라.

 

회전 가능성을 우선 나열한다.

 

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경우 분기가 가능하다.

 

1. left가 최소인 경우

2. mid가 최소인 경우

3. right 가 최소인 경우

 

left가 최소인 경우는 그냥 left 값이 답이다. 

mid가 최소인 경우는 mid가 최소이거나 left side에 답이 있다.

right가 최소인 경우는 right가 최소이거나 right side에 답이 있다.

 

로직대로 코드를 만든다.

int findMinBS(vector<int>& nums, int left, int right)
{
    if (left > right)    -1;

    int mid = left + (right - left) / 2;

    // 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 

    if (nums[left] <= nums[mid] && nums[left] <= nums[right])
        return nums[left];
    else if (nums[left] >= nums[mid] && nums[mid] <= nums[right])
    {
        if(mid>0 && nums[mid]<=nums[mid-1])        return nums[mid];
        return findMinBS(nums, left, mid-1);
    }
    else 
    {
        if(right>0 && nums[right-1]>=nums[right])  return nums[right];
        return findMinBS(nums, mid+1, right);
    }
}

int findMin(vector<int>& nums) 
{
   return findMinBS(nums, 0, nums.size() - 1);
}

 

결과