[LeetCode # 153] Find Minimum in Rotated Sorted Array

주어진 문제는, 어떤 배열이 주어졌을 때 그 배열에서 가장 작은 값을 찾는 문제이다. 이 때, 배열은 정렬된 배열을 rotation 시킨 배열로 주어진다.

 

예를 들어, [0, 1, 2, 3, 4, 5, 6, 7] 과 같이 정렬된 배열이 주어질 수도 있고 [4, 5, 6, 7, 0, 1, 2, 3] 과 같이 앞의 정렬된 배열에서 [0, 1, 2, 3] 의 위치가 뒤로 이동한 배열이 주어질 수도 있다.

 

이 문제에서 주어진 조건은, 문제 해결 시 O(log n) 의 시간복잡도를 갖는 알고리즘을 사용해야 한다는 것이다.

 

문제 해결 전략은 다음과 같다. 기본적으로 이분 탐색을 사용해 배열을 반씩 분할해 각 분할마다 최소값을 찾고, 그 중 가장 최소값을 찾는다.

로테이션이 된 배열이기 때문에, 전체 배열은 정렬이 되지 않은 상태일 수 있지만 부분 배열은 정렬이 된 상태일 수 있다. 위의 [4, 5, 6, 7, 0, 1, 2, 3] 의 배열을 반으로 분할해 보면, [4, 5, 6, 7], [0, 1, 2, 3] 과 같이 표현된다. 이 때 각 부분배열은 모두 정렬된 상태이므로 최소값을 쉽게 찾을 수 있다.

 

만약, 분할된 부분배열이 정렬되지 않은 배열일지라도, 예를 들어 [4, 5, 0] 이라고 하면 이러한 배열은 다시 또 분할을 해서 정렬된 상태가 될 때까지 분할을 하면 된다. 계속 반으로 분할을 하다보면, 언젠가는 정렬된 부분배열이 될 것이고 (혹은 한 개의 원소만 남은 배열이 되거나) 그 때의 최소값은 바로 탐색할 수 있기 때문에 이 방법은 O(log n) 의 시간복잡도를 갖는 알고리즘이라 할 수 있다.

 

위와 같은 풀이로 작성한 소스 코드는 다음과 같다.

 

class Solution {
public:
    int binarySearch(vector<int>& nums, int s, int e) {
        if (s >= e) {
            return nums[s];
        }
        if (nums[s] < nums[e]) {
            return nums[s];
        }

        int m = (s + e) / 2;
        int l = binarySearch(nums, s, m);
        int r = binarySearch(nums, m + 1, e);
        return l < r ? l : r;
    }
    int findMin(vector<int> &nums) {
        int min = binarySearch(nums, 0, nums.size() - 1);
        return min;
    }
};