[Leetcode] 153. Find Minimum in Rotated Sorted Array

Problem:

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.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.
Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.
Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 
 

Constraints:

n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
All the integers of nums are unique.
nums is sorted and rotated between 1 and n times.

 

Solution:

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

findpivot함수를 만들었다. 이 함수는 minimum값을 찾는 함수다. 즉, 오름차순이 끊기는 지점을 찾는 함수다. 그 지점이 곳 최솟값이 존재하는 index이기 때문이다. 그렇게 하기 위해서 처음에 nums [mid] == nums [right]를 설정하였다. 나는 right값을 기준으로 mid값을 분석하였다. 

이때, nums[mid] < nums [right]를 만족하면 right = mid로 바꾸었다. right = mid - 1으로 바꾸지 않은 이유는 예시를 들어 설명하겠다. 

만약에, [1,2]이라는 리스트가 있다고 가정하자. 이때 ,left = 0 , right = 1이다. mid = 0이다. nums [mid] < nums [right]를 만족하기 때문에 , right = mid -1 = -1이 된다. 즉, 최솟값이 아닌 최솟값 이전의 값 또는 None이 출력될 수 있다. 따라서 right =mid로 설정해 준다. 

다음으로, nums[mid] > nums [right]를 만족하면, left = mid + 1로 설정해 준다.