leet code 153 - Find Minimum in Rotated Sorted Array

이진 탐색의 변형 문제이다.

볼 수 있는 키워드는 일단 고유값, 오름 차순의 정렬. log n의 시간 복잡도, 최소값의 탐색

 

하지만 rotate돼 있고 , 특정값이 주어지는게 아닌, 임의의 최소값을 찾는 문제이기 때문에 일반적 이진탐색 문제는 아님을 알 수 있다.

 

---

 

아래는 기본 이진탐색 알고리즘이다.

 

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

 

각 각 l, r포인터를 두고, 중간 인덱스의 값과 대소를 비교해 오른쪽 범위인지 왼쪽 범위인지 포인터를 조절해 탐색 범위를 조절해 나간다.

 

O(log n)

 

---

이진 탐색 알고리즘응용 풀이

 

class Solution:
    def findMin(self, nums: List[int]) -> int:
        #최소값을 구하라. 제약조건 log n
        #최소값이 리스트 맨 뒤에 있다면?


        res = nums[0]
        l, r =0, len(nums) - 1

        while l <= r:
            if nums[l] < nums[r]:
                res = min(res, nums[l])
                break

            m = (l+r) // 2
            res = min(res, nums[m])

            if nums[m] >= nums[l]:
                l = m + 1
            else:
                r = m - 1
            


        return res

 

일단 l, r을 포인터로 선언해준다.

 

res는 이미 정렬된 최선의 상황을 가정 리스트의 맨 앞 인덱스 값으로 초기화 해준다.

rotate는 오른쪽 끝단위치 값이 왼쪽끝단의 위치로 이동하며 일어난다. 즉 rotate가 딱 n * x 만큼만 일어나지 않았다면,  왼쪽의 값이 오른쪽 값보다 항상 클 수 밖에 없다.

 

이후 왼쪽 포인터가 오른쪽 포인터보다 작거나 같다는 조건아래 while문 실행.

 

먼저 l포인터와 r 포인터 의 인덱스에 해당하는 값을 비교해준다( 이미 정렬돼 있는 최선의 상황)

(맨 초기의 상황만을 말하는게 아니다. 탐색 범위를 좁혔을때에도 좁힌 범위가 이미 정렬돼 있는 상태일 수 있다.

 

example [4,5,6,7,0,1,2]

 

비교 하에 이미 정렬 돼 있다면 res와 왼쪽 포인터 값을 비교, 더 작은 값을 결과 값으로 갱신해주고 break한다.

 

그 다음으로 중간 포인터의 갱신.

m = (l + r) // 2

 

중간값과 res값을 비교해 최소값을 res에 넣어준다.

 

이후는 m포인터가 어떻게 범위를 좁힐 것이냐에 대한 분기. 

중앙 포인터에 해당 하는 값이 왼쪽 포인터에 해당하는 값보다 크거나 같다면 오른쪽 범위를 탐색한다.

알다시피 rotate는 오른쪽 끝단위치 값이 왼쪽끝단의 위치로 이동하며 일어난다. 중앙 값이 최 왼쪽 값보다 크거나 같다면 이미 최소값이 오른쪽에 있도록 순회가 일어난 상태가 된다.[4,5,6,7,0,1,2] [(첫인덱스부터 중앙값까지 오름차순 정렬된 상태일 것이다.)

만약 중앙 값이 최왼쪽 값보다 작다면 [7,0,1,2,3,4,5,6,] 최소값이 왼쪽에 있는 상태가 된다.