[Leetcode] 153. Find Minimum in Rotated Sorted Array

Identifying the Problem

오름차순이 Rotated 된 수열에서 가장 작은 값을 구하라

오름차순이 rotated 되었단 뜻은  

[1,2,3,4]가 있으면, [1,2,3,4] → [2,3,4,1] → [3,4,1,2]는 2번 rotated 된 것이다. 

단 시간 복잡도는 O(log(n))이 되어야 한다.

 

Organizing thoughts

시간 복잡도가  logn이 되려면 이진 탐색을 해야 한다.

 

우선 rotated 된 수열이 어떤 패턴이 있는지 알아보자

[1,2,3,4,5] 같은 경우 가운데를 기준으로 양 끝을 비교하면

1 <3 <5로 왼쪽과 오른쪽 둘 다 오름차순인 것을 확인할 수 있다.

 

[3,4,5,1,2] 같은 경우 

3<5 , 5>2로 왼쪽은 오름차순이지만 왼쪽은 내림차순인 것을 확인할 수 있다.

 

[4,5,1,2,3] 같은 경우

4>1 , 1 <3로 왼쪽은 내림차순이지만 오른쪽은 오름차순인 것을 확인할 수 있다.

 

이런 식으로 하나의 수열을 rotate 시키면서 확인해 보면

왼쪽	오른쪽
오름차순	오름차순
오름차순	내림차순
내림차순	오름차순

이런식으로 나오고, 내림차순 내림차순인 경우는 나오지 않는다.

또한 최솟값은 내림차순인 쪽에만 있음을 확인할 수 있다.

이 부분이 문제의 핵심이다.

 

직접 해보는 게 잘 이해된다!!

 

따라서

1. Left, Mid, Right를 정하고

2. 왼쪽 오른쪽 둘 다 오름차순인 경우에는 Left 리턴

3. 왼쪽이 내림차순인 경우

3-1 Right 값을 Mid로

4. 오른쪽이 오름차순인 경우 

4-1 Left 값을 Mid로 정하며 탐색 범위를 줄여나간다.

Sourcecode

int findMin(int* nums, int numsSize)
{
    int L = 0;
    int R = numsSize - 1;
    int mid = (L+R)/2;
    
    if(nums[L] <= nums[mid] && nums[mid] <= nums[R])
        return nums[L];
    
    while(L!= mid)
    {
        if(nums[L] > nums[mid])
            R = mid;
        else if(nums[mid] > nums[R])
            L = mid;
        
        
        mid = (R+L)/2;
        
        
    }
    return nums[R];
        
}