[Leetcode] 153. Find Minimum in Rotated Sorted Array - 주옥같은 binary search

1. 문제링크

Find Minimum in Rotated Sorted Array - LeetCode

 

 

2. Rotated Sorted Array는 무엇인가

- Sorted Array : 오름차순 배열 {1, 2, 3, 4, 5}

- Rotated : random한 곳에서 꼬였다 {3, 4, 5, 1, 2} or {4, 5, 0, 1, 2, 3}.. 등등

 

 

3. search할 영역을 잘 생각해보자 (m은 뻐킹 갈림길이며 왼쪽으로 갈 지 오른쪽으로 갈 지 결정해야함)

이 주옥같은 문제는 time complexcity가 O(log n)이 되어야함

O(log n)은 모다? binary search를 해야한다는 것이다

 

binary search니까 l, r포인터를 두개 가지고 m을 찾아서 값을 비교한다

여기서 m은 l와 r의 중간값이다 

이 m은 주옥같은 갈림길이며 m의 값을 확인하면 m의 왼쪽이나 오른쪽만 탐색할 수 있다

 

nums = {4, 5, 6, 0, 1} 이고 l = 0,  r = 4, m =2라고 하자

nums[l] <= nums[m] 이라는건 뭐다? l에서 m까지는 오름차순이라는 것이다

그럼 nums[l] to nums[m] 사이의 값 중에서는 nums[l]이 제일 미니한 값이므로 

현재 가지고 있는 최솟값이랑 비교하여 갱신한다

 

그럼 l to m 까지의 최소값을 찾았으니 우리는 더이상 m의 왼쪽길을 탐색하지 않아도 된다

오른쪽 길만 탐색하면 되니께 l포인터 값을 m + 1으로 갱신해주자

 

nums[l] > nums[m]인 경우를 생각해보자

nums = {4, 0, 1, 2, 3}이고 l = 0,  r = 4, m =2인 경우가 이 조건에 해당한다

nums[l] > nums[m]라는 것은 이 사이에 뻐킹 pivot (nums 배열에서 최솟값인 놈)이 존재한다는 뜻이다

그럼 l to m 사이에 최솟값이 있는것이 보장되었으니 우리는 오른쪽 길을 탐색할 필요가 없다

r 포인터 값을 m - 1로 갱신하자

 

마지막으로 nums[l] < nums[r]이라면 드디어 nums[l] to nums[r] 는 아름다운 오름차순이라는 것이다

멍뭉이도 알겠찌만 nums[l] < nums[r]라는 것은 nums[l]이 여기서는 최솟값이므로

현재 가지고 있는 최솟값이랑 비교하고 갱신하며 주옥같은 미궁를 빠져나가면 되겠다 (break)

 

 

4. solution

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size()-1;
        int res = nums[0];
        while(l <= r){
            if(nums[l] < nums[r]){
                res = min(res, nums[l]);
                break;                
            }
            int m = (l + r) / 2;
            res = min(res, nums[m]);
            if(nums[l] <= nums[m])
                l = m + 1;
            else
                r = m -1;
        }

        return res;
    }
};