[LeetCode] 153. Find Minimum in Rotated Sorted Array

*알고리즘 스터디에 참여하면서 Blind 75 LeetCode Questions 목록에 있는 문제를 풀이합니다.

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

Find Minimum in Rotated Sorted Array - LeetCode

 

문제 해설

오름차순으로 정렬된 길이가 n인 배열이 1번에서 n번 회전한다고 가정합니다. 예를 들어 배열 nums = [0,1,2,4,5,6,7]은 다음과 같을 수 있습니다.

• 4번 회전한다면, [4,5,6,7,0,1,2].
• 7번 회전한다면 [0,1,2,4,5,6,7].

주어진 배열의 최소 요소를 반환해야 합니다. 배열에 중복 항목은 없다고 가정할 수 있습니다. 
시간복잡도는 O(log n)으로 지정합니다.

---

풀이

class Solution:
    def findMin(self, nums: List[int]) -> int:
        l, r = 0, len(nums)-1
        while l < r:
            mid = (l+r)//2
            if nums[mid] > nums[r]:
                l = mid+1
            else:
                r = mid
        return nums[l]