LeetCode 153 - Find Minimum in Rotated Sorted Array

중복이 없는 오름차순 배열이 한 번 회전된 상태에서 최솟값을 찾는 Medium 문제다. 배열의 절반을 버리기 위해 mid 값과 오른쪽 끝 값을 비교했고, 탐색 구간이 한 칸으로 줄어들 때까지 경계를 갱신했다.

문제 링크 & 설명

문제 링크: 153. Find Minimum in Rotated Sorted Array
요약: 서로 다른 값으로 이루어진 정렬 배열이 회전되어 있을 때, O(log n) 시간에 최솟값을 반환하는 문제다.

예를 들어 [4, 5, 6, 7, 0, 1, 2]는 원래 정렬된 배열의 일부를 앞으로 옮긴 형태다. 최솟값 0은 값이 갑자기 작아지는 회전 경계에 있으며, 이 경계가 어느 절반에 있는지 판단하면 이진 탐색을 적용할 수 있다.

접근 방법

left와 right는 최솟값이 들어 있을 수 있는 탐색 구간을 나타낸다. 매 반복에서 가운데 인덱스인 pivot을 구하고 nums[pivot]과 nums[right]를 비교한다.

pivot = left + (right - left) // 2

nums[pivot]이 nums[right]보다 작다면 pivot부터 right까지는 오름차순으로 정렬된 구간이다. 최솟값은 pivot 자체이거나 그 왼쪽에 있으므로 pivot을 버리지 않고 right를 pivot으로 옮긴다.

if nums[pivot] < nums[right]:
    right = pivot

반대로 nums[pivot]이 nums[right]보다 크다면 회전 경계는 pivot 오른쪽에 있다. pivot은 최솟값일 수 없으므로 left를 pivot + 1로 옮긴다.

else:
    left = pivot + 1

left와 right가 같은 위치에서 만나면 그 인덱스가 최솟값의 위치다.

트러블 슈팅

처음에는 nums[left]와 nums[right]를 비교해 어느 쪽으로 이동할지 정하려고 했지만, 이 비교만으로는 최솟값이 들어 있는 절반을 안정적으로 구분할 수 없었다. 탐색 경계의 양 끝이 모두 회전 이후의 정렬 관계에 포함될 수 있고, left 값만으로는 가운데를 포함한 어느 절반을 버려야 하는지 결정되지 않기 때문이다.

비교 기준을 nums[pivot]과 nums[right]로 바꾸면 오른쪽 절반의 정렬 여부를 매 반복에서 판단할 수 있다. pivot 값이 더 작으면 pivot을 포함한 왼쪽 구간을 남기고, 더 크면 회전 경계가 오른쪽에 있으므로 pivot까지 제외한다.

복잡도 분석

시간 복잡도: O(log n)
- 반복할 때마다 최솟값 후보 구간을 절반으로 줄인다.
공간 복잡도: O(1)
- left, right, pivot 인덱스만 사용한다.

구현 코드

from typing import List

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1

        while left < right:
            pivot = left + (right - left) // 2

            if nums[pivot] < nums[right]:
                right = pivot
            else:
                left = pivot + 1

        return nums[right]

요약 및 회고

이진 탐색에서 필요한 것은 단순한 값 비교가 아니라, 그 비교로 어느 구간에 최솟값이 남아 있는지 증명하는 기준이다. mid와 right를 비교하면 오른쪽 구간의 정렬 여부를 판단할 수 있고, 최솟값 후보를 잃지 않으면서 탐색 범위를 절반씩 줄일 수 있다.