leetcode 153 - Find Minimum in Rotated Sorted Array

이 문제는 O(logN)으로 풀라고 나와있다. logN으로 주어진 것이면 우리는 binary search라는 것을 직감적으로 알아야한다. 바로 최소값을 찾기 위한 여정을 해야하는데, 안타깝게도 좌로 n번이 회전이 되어있는 array안에서 찾아야한다.

 

이런 경우에는 우리는 문제에 어떻게 다가갈 것인지 생각을 해봐야한다.

 

즉 mid로 항상 중앙에 위치한 값을 찾으면서, 역전이 일어난 부분이 있다면 그 부분이 변곡이 일어난 곳이며, 각 최대값 또는 최소값이 해당 mid 주변에 위치해있다는 뜻이다.

 

완성된 코드는 아래와 같다

 

class Solution(object):
    def findMin(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        if len(nums) == 1 :
            return nums[0]
        
        left = 0
        right = len(nums) - 1
        
        if nums[0] < nums[right]:
            return nums[0]
        
        while right >= left:
            mid = left + (right - left)/2
            
            
            if nums[mid] > nums[mid+1]:
                return nums[mid+1]
        
            if nums[mid-1] > nums[mid]:
                return nums[mid]
                          
            
            
            if nums[mid] > nums[left]:
                left = mid+1            
            else :
                right = mid-1