[DSA][Binary Search] 04. Find Minimum in Rotated Sorted Array

LeetCode 153

 

04. Find Minimum in Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
- [4,5,6,7,0,1,2] if it was rotated 4 times.
- [0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.

 

 

[질문하기]

- 배열에 중복된 값이 포함될 수 있나요? NO

- 값이 연속적으로 증가하나요? NO

 

 

[아이디어]

- mid 인덱스의 값과 r 인덱스의 값을 비교하여 최솟값이 있을 구간을 추적하자.

 

 

[풀이 1] Binary Search

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums) - 1

        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] < nums[r]:
                r = mid
            else:
                l = mid + 1
        
        return nums[l]

배열을 앞에서부터 순회하면서 값이 작아지는 부분을 찾으면 O(n) 시간에 답을 찾을 수 있다.

하지만 이 배열은 정렬된 상태에서 회전된 것이기 때문에, 적어도 하나의 절반 구간은 항상 정렬되어 있다. 따라서 이진탐색을 사용하면 정렬된 절반에 대한 불필요한 탐색을 줄일 수 있다. 이진 탐색을 하면서 중간값 mid와 r을 비교했을 때, nums[mid] < nums[r]라면, mid ~ r 구간이 정렬되어 있고, 이 안에는 최솟값이 존재하지 않거나 mid일 수 있다. 따라서 왼쪽 구간에 최솟값이 있기 때문에 right = mid로 좁힐 수 있다. 반대로 nums[mid] > nums[r]인 경우, 최솟값은 반드시 mid + 1 ~ r 사이에 있다는 뜻이므로 left = mid + 1로 갱신할 수 있다.

 

⨳ nums[l] < nums[mid]로도 정렬 여부는 판단할 수 있지만, 최솟값이 mid보다 오른쪽에 있을지 왼쪽에 있을지 판단할 수 없기 때문에, r을 기준으로 비교하는 것이 안전하다.

 

 

⏱️ 시간복잡도

길이 n의 배열을 이진탐색으로 순회하므로 시간복잡도는 O(logn)이다.

🧠 공간복잡도

추가적인 공간을 사용하지 않고, 이진탐색을 위한 변수만을 사용하기 때문에 O(1)의 공간 복잡도를 갖는다.