← 전체 회차
A-031● Day 312026.06.06mediumleetcode #153neetcode150

회전된 정렬 배열에서 최솟값 찾기

#array#binary-search
↗ leetcode #153 · find-minimum-in-rotated-sorted-array
01

문제

· problem
P.031

회전된 정렬 배열에서 최솟값 찾기

↗ leetcode #153

길이 n인 오름차순 정렬 배열이 1번에서 n번 사이로 회전되었다고 하자. 예를 들어, 배열 [0,1,2,4,5,6,7]은 4번 회전되면 [4,5,6,7,0,1,2]가 된다. 배열 [a[0], a[1], a[2], ..., a[n-1]]을 1번 회전하면 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]가 된다. 고유한 원소들로 이루어진 정렬되고 회전된 배열 nums가 주어졌을 때, 이 배열의 최솟값을 구하시오. O(log n) 시간 복잡도의 알고리즘을 작성해야 한다.

제약
  • · 1 ≤ n ≤ 5000
  • · -5000 ≤ nums[i] ≤ 5000
  • · All elements are unique
  • · Array is sorted and rotated between 1 and n times
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[3,4,5,1,2]
1
example 2input → output
[4,5,6,7,0,1,2]
0
example 3input → output
[11,13,15,17]
11
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    최솟값 그 자체를 반환해야 하나요, 아니면 그 인덱스를 반환해야 하나요?
  • ☐
    배열이 회전되지 않은 경우(예: [11,13,15,17])도 처리해야 하나요?
  • ☐
    배열에 중복된 원소가 있을 수 있나요?
  • ☐
    파이썬의 내장 min() 함수를 사용하면 안 되나요?
  • ☐
    선형 탐색으로도 O(log n) 성능을 얻을 수 있나요?
  • ☐
    배열을 두 부분으로 나누면, 항상 한 쪽은 정렬되어 있나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 탐색 범위와 최솟값 초기화
○
start , end = 0, len(nums) - 1
○
start, end = 1, len(nums) - 2
○
start, end = 0, len(nums)
step 2· 이진 탐색 루프
○
while start  <  end :
○
while start <= end:
○
while start < end - 1:
step 3· 중간값 계산 및 최솟값 업데이트│ 중첩
○
mid = start + (end - start ) // 2
○
mid = (start + end) // 2
○
mid = start + (end - start) // 2
curr_min = nums[mid]
step 4· 탐색 방향 결정│ 중첩
○
if nums[mid] > nums[end]:
○
if nums[mid] > nums[start]:
○
if nums[mid] < nums[end]:
step 5· 왼쪽 경계 이동│ │ 중첩
○
start = mid + 1
○
start = mid
○
start = mid - 1
step 6· 오른쪽 경계 이동│ │ 중첩
○
end = mid - 1
○
end = mid
○
end = mid + 1
step 7· 최종 최솟값 반환
○
return min(curr_min,nums[start])
○
return curr_min
○
return nums[start]
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

· solve
solution.py
1
class Solution:
2
    def findMin(self, nums: List[int]) -> int:
3
        start , end = 0, len(nums) - 1
4
        curr_min = float("inf")
5
6
        while start  <  end :
7
            mid = start + (end - start ) // 2
8
            curr_min = min(curr_min,nums[mid])
9
10
            # right has the min
11
            if nums[mid] > nums[end]:
12
                start = mid + 1
13
14
            # left has the  min
15
            else:
16
                end = mid - 1
17
18
        return min(curr_min,nums[start])
머릿속 dry-run 케이스
// 각 케이스를 머릿속으로 따라가보세요. 막히면 아래 worked example 펼침.
case 1
[3,4,5,1,2]
→
1
case 2
[4,5,6,7,0,1,2]
→
0
case 3
[11,13,15,17]
→
11
// UI 가 walk-through 안 함 — 학습자가 머릿속으로. 막히면 worked example 펼침.