← 전체 회차
A-032● Day 322026.06.07mediumleetcode #33neetcode150

회전된 정렬 배열에서 검색

#array#binary-search
↗ leetcode #33 · search-in-rotated-sorted-array
01

문제

· problem
P.032

회전된 정렬 배열에서 검색

↗ leetcode #33

정수 배열 nums가 오름차순으로 정렬되어 있습니다 (모든 값이 서로 다릅니다). 함수에 전달되기 전에, nums는 미지의 인덱스 k (1 <= k < nums.length)에서 왼쪽으로 회전된 상태일 수 있습니다. 회전된 배열은 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] 형태입니다 (0-인덱싱). 예를 들어, [0,1,2,4,5,6,7]을 3만큼 왼쪽으로 회전하면 [4,5,6,7,0,1,2]가 됩니다. 회전된 후의 배열 nums와 정수 target이 주어질 때, target이 nums에 있으면 그 인덱스를, 없으면 -1을 반환하세요. O(log n) 시간 복잡도로 작동하는 알고리즘을 작성해야 합니다.

제약
  • · 1 ≤ nums.length ≤ 5000
  • · -10⁴ ≤ nums[i] ≤ 10⁴
  • · All values in nums are unique
  • · nums is an ascending array that is possibly rotated
  • · -10⁴ ≤ target ≤ 10⁴
// 지문은 본인 언어 요약 — 원문은 위 링크에서
입출력 예시
example 1input → output
[4,5,6,7,0,1,2]
0
4
example 2input → output
[4,5,6,7,0,1,2]
3
-1
example 3input → output
[1]
0
-1
02

사전 사고

· pre-solve
● 1리스트 출력→● 2선택→● 3정답 공개
  • ☐
    배열이 '회전될 가능성'이 있다는 것이 무엇을 의미하나요?
  • ☐
    회전된 배열에서 이진 탐색이 어떻게 작동하나요?
  • ☐
    중점을 기준으로 배열의 어느 쪽이 정렬되어 있는지 어떻게 판단하나요?
  • ☐
    정렬된 부분을 파악한 후 다음 단계는 무엇인가요?
  • ☐
    배열이 반드시 회전되어 있다고 보장되나요?
  • ☐
    배열 크기가 작으므로 선형 탐색을 사용해도 되나요?
  • ☐
    배열에 중복된 값이 있을 수 있나요?
던질 질문에 체크하고 확인을 누르세요
// 결과는 세션 메모리만 — 새로고침하면 초기화됩니다 (반복 학습)
03

논리 구조

· logic
● 1슬롯 출력→● 2슬롯별 선택→● 3정답 공개
// 각 슬롯에 들어갈 코드 한 줄을 골라 알고리즘 흐름을 합성해보세요. 코드는 안 짜지만 논리 뼈대는 직접.
step 1· 포인터 초기화
○
l, r = 0, len(nums) - 1
○
l, r = 0, len(nums)
○
l, r = 1, len(nums) - 1
step 2· 이진 탐색 루프
○
while l <= r:
○
while l < r:
○
while l < len(nums) and r >= 0:
step 3· 중점 계산│ 중첩
○
mid = (l + r) // 2
○
mid = (l + r) / 2
○
mid = r - (r - l) // 2
step 4· 타겟 발견 확인│ 중첩
○
if target == nums[mid]:
○
if target < nums[mid]:
○
if target >= nums[mid]:
step 5· 정렬된 부분 판단│ 중첩
○
if nums[l] <= nums[mid]:
○
if nums[mid] <= nums[r]:
○
if nums[l] > nums[mid]:
step 6· 검색 범위 조정│ │ 중첩
○
if target > nums[mid] or target < nums[l]:
○
if target > nums[mid] or target > nums[l]:
○
if target < nums[mid] or target < nums[l]:
step 7· 검색 실패 반환
○
return -1
○
return 0
○
return None
각 슬롯에 한 줄씩 골라보세요
// format: slot — 다른 패턴(재귀·DP 등) 은 ordering·state-first 등 별도 format. ADR-08 후속.
04

문제풀이 · 트레이스

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