[LeetCode] 153. Find Minimum in Rotated Sorted Array

🎨 문제

오름차순으로 정렬된 배열을 회전시킨 배열이 주어진다. 해당 배열의 최소값을 찾는 문제이다. 단, 시간복잡도는 O(logN)

Find Minimum in Rotated Sorted Array - LeetCode

📘 풀이

[LeetCode] 33. Search in Rotated Sorted Array

이전에 주인장이 풀었던 문제를 참고하면 좋다.

문제에 주어진 조건을 간단히 해보자

조건

1. 정렬된 배열을 회전시켰다.

2. O(logN)

 

위 두 가지 조건으로 알 수 있는 것이 있다. 배열은 최대 두 부분으로 정렬되어 있다는 점과 이진탐색을 사용해야 한다는 점이다. 1번 조건부터 살펴보겠다.

 

배열의 상태는 두 가지 존재한다.

 

1. 두 부분으로 정렬된 상태

2. 완전히 정렬된 상태

 

그림으로 나타내면 다음과 같다.

두 부분으로 정렬된 상태

완전히 정렬된 상태

하지만 배열 전체의 상태를 한 번에 알 수 없으므로 기본적으로 두 부분으로 정렬된 상태라 가정하겠다. 이 경우 Mid 의 위치는 두 가지로 나타낼 수 있다.

범위에 따른 Mid의 위치

Mid의 위치는 최소값이 존재하는 정렬된 범위와 그 반대의 경우에 존재할 수 있다. 이 두 경우를 나누어 이진탐색하면 된다. 

public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while(left < right) {		// left == right일 때 최소값
            int mid = (left + right) / 2;

            if (nums[right] < nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return nums[left];
    }

풀이에서 right를 기준으로 Mid의 위치를 구분할 수 있었다. 그렇다면 left로도 가능한지 의문이 생긴다. 하지만 left로 구분하기에는 무리가 있다. 필자의 생각으로는 그 이유는 오름차순으로 정렬되어 있기 때문이다.

완전히 정렬된 상태

Left를 기준으로 조건문을 작성하면 nums[left] < nums[mid] 일 경우 left를 mid로 가져와야 한다. 하지만 완전히 정렬된 상태를 고려한다면 nums[left]가 최소가 되기 때문에 rigth를 기준으로 잡았다.