[leetcode] 153. Find Minimum in Rotated Sorted Array 파이썬 코드

정렬된 배열에서 최솟값을 찾는 문제다. 그런데 완전히 정렬된 배열은 아니다. rotate되지 않았으면 가지런히 정렬된 배열이었겠지만, 한 번 rotated 되었기 때문에 정렬된 2개의 덩어리가 있다. 여기서 O(logn) 만에 최솟값을 찾아야 한다. 정렬과 주어진 시간 복잡도를 봤을 때 이진탐색을 써야 한다. 그런데 문제도 살짝 달라졌으니 이진 탐색 코드도 살짝 달라져야겠다.

 

left pointer, right pointer, mid pointer를 둔다.

mid pointer와 left pointer를 비교한다. 그래서 왼쪽이 가운데보다 작다면, (1) 이건 한 쪽이 정렬된 배열이니까 가장 왼쪽에 있는 값을 최솟값으로 두고, (2) left pointer를 mid+1로 옮겨서 오른쪽 배열을 봐야 한다.

 

왼쪽이 더 크다면, 중간에 작은 값이 있다는 말이므로 right pointer를 mid-1로 옮겨서 왼쪽 배열을 탐색해야 한다.

 

그런데 이렇게 로직을 짜서 틀렸다.

 

[2, 1] 이라는 배열이 있을 수 있다. 그래서 '왼쪽이 가운데보다 작다면'이라는 조건을 '작거나 같다면'으로 바꿔줘야 한다.

 

class Solution(object):
    def findMin(self, nums):
        if len(nums) == 1: 
            return nums[0]

        result = 5001
        lp, rp = 0, len(nums)-1
        while lp <= rp:
            mid = (lp + rp) // 2
            if nums[lp] <= nums[mid]: # 왼쪽이 가운데보다 작거나 같다면
                if nums[lp] < result: result = nums[lp]
                lp = mid + 1
            else: 
                if nums[mid] < result: result = nums[mid]
                rp = mid - 1

        return result