competitive-programming2021년 12월 29일1분 분량

[LeetCode] 153. Find Minimum in Rotated Sorted Array 풀이

수정일: 2021년 12월 29일

Binary search

지원 언어:enko

#Problem

153. Find Minimum in Rotated Sorted Array

#Approach

이진탐색으로 $nums[l]$ , $nums[m]$ , $nums[r]$ 값을 비교해준다.

$nums[l] \le nums[m]$ 이면:
최솟값은 index $m$ 보다 오른쪽에 있다.

l <- m+1;

아니면:
최솟값은 $nums[m]$ 자체이거나, index $m$ 보다 왼쪽에 있다.

r <- m;

#Code

/**
 * written: 2021. 12. 29. Wed. 15:51:07 [UTC+9]
 * jooncco의 mac에서.
 **/

typedef vector<int> vi;

class Solution {
public:
    int findMin(vi &nums) {
        int n= nums.size();
        // size가 1이거나 rotate가 일어나지 않은 경우
        if (n == 1 || nums[0] < nums[n-1]) return nums[0];

        int l= 0, r= n-1;
        while (l < r) {
            int m= l+(r-l)/2;
            // nums[l], nums[m], nums[r] 값을 비교.
            // nums[l] < nums[r]인 경우에 대한 예외처리를 포함
            if (nums[l] <= nums[m] && nums[l] > nums[r]) l= m+1;
            else r= m;
        }
        // l: 최소 index
        return nums[l];
    }
};

#Complexity

Time: $O(\log n)$
Space: $O(1)$