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.

풀이

• O(logn)의 풀이만 가능
• 정렬상태에서 회전된 배열에서 최솟값을 찾기 위해 이진 탐색을 사용
• 주어진 배열을 왼쪽과 오른쪽으로 나눔
• if nums[start] > nums[mid]: 최솟값은 왼쪽에 존재
• else: 최솟값은 오른쪽에 존재

수도 코드

start, end = 0, len(nums) - 1

while start < end:
	mid = (start + end) // 2
    
    if 왼쪽에 최솟값이 있음:
    	end = mid # 범위를 줄임
    else: # 오른쪽
    	start = mid + 1
return nums[start] # 최솟값

Solution(Runtime: 46ms)

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