0Pricing
DSA Interview Prep · 강의

회전 배열과 정렬되지 않은 배열의 이진 검색

각 단계에서 어느 절반이 정렬되어 있는지 판단해 search-in-rotated-sorted-array와 find-minimum-in-rotated-array를 해결합니다.

회전 배열과 정렬되지 않은 배열의 이진 검색은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

회전된 정렬 배열이란?

회전된 정렬 배열은 어떤 피벗에서 정렬된 배열을 잘라 두 부분의 순서를 서로 바꾼 배열입니다. 예를 들어 [4, 5, 6, 7, 0, 1, 2]는 정렬된 배열 [0,1,2,4,5,6,7]을 인덱스 4에서 회전한 것입니다. 배열 전체가 더 이상 정렬되어 있지 않으므로 표준 이진 탐색은 여기서 실패합니다.

핵심 통찰은 어떤 방식으로 회전하더라도 배열의 적어도 한쪽 절반은 항상 정렬되어 있다는 점입니다. 경계를 어디로 이동할지 결정하기 전에 이진 탐색으로 어느 절반이 정렬되어 있는지 식별해야 합니다.

# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossing

정렬된 절반 식별

mid를 계산한 후 arr[lo]와 arr[mid]를 비교합니다. arr[lo] <= arr[mid]이면 왼쪽 절반이 정렬되어 있습니다. 그렇지 않으면 오른쪽 절반이 정렬되어 있습니다. 어느 절반이 정렬되어 있는지 알게 되면 대상값이 해당 정렬된 범위에 포함되는지 확인하고 그에 따라 탐색 범위를 좁힐 수 있습니다.

이 결정 트리를 사용하면 단계마다 배열의 정확히 절반을 버릴 수 있으므로, 회전된 배열에서도 O(log n)의 시간 복잡도를 유지합니다.

def search_rotated(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        # Left half is sorted
        if nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0))  # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3))  # -1

예제를 따라가며 확인하기

search_rotated([4,5,6,7,0,1,2], 0)을 단계별로 따라가 보겠습니다. 처음에는 lo=0, hi=6, mid=3, arr[mid]=7입니다. 대상값 0이 정렬된 왼쪽 절반 [4..7]에 있습니까? 아니므로 lo=4로 이동합니다. 이제 lo=4, hi=6, mid=5, arr[mid]=1입니다. 왼쪽 절반 [0,1]이 정렬되어 있습니다(arr[lo]=0 <= arr[mid]=1). 0이 [0..1)에 있습니까? 그렇습니다. 따라서 hi=4로 설정합니다. 이제 lo=4, hi=4, mid=4, arr[4]=0이므로 인덱스 4에서 찾았습니다.

# Step-by-step trace
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
steps = []
lo, hi = 0, len(nums) - 1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    steps.append(f'lo={lo} hi={hi} mid={mid} val={nums[mid]}')
    if nums[mid] == target:
        steps.append(f'Found at {mid}')
        break
    if nums[lo] <= nums[mid]:
        if nums[lo] <= target < nums[mid]:
            hi = mid - 1
        else:
            lo = mid + 1
    else:
        if nums[mid] < target <= nums[hi]:
            lo = mid + 1
        else:
            hi = mid - 1
for s in steps:
    print(s)

회전에서 중복 처리하기

회전된 배열에 중복값이 포함될 수 있다면(예: [1,3,1,1,1]), nums[lo] == nums[mid] 조건은 모호해져 어느 절반이 정렬되었는지 알 수 없습니다. 안전한 해결 방법은 lo를 1 증가시키거나 hi를 1 감소시킨 후 다시 시도하는 것입니다. 이렇게 하면 최악의 경우 시간 복잡도가 O(n)으로 늘어나므로 면접관에게 반드시 설명해야 합니다.

def search_rotated_with_dups(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return True
        # Ambiguous: shrink left boundary
        if nums[lo] == nums[mid] == nums[hi]:
            lo += 1
            hi -= 1
        elif nums[lo] <= nums[mid]:
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return False

print(search_rotated_with_dups([1, 3, 1, 1, 1], 3))  # True
print(search_rotated_with_dups([2, 2, 2, 0, 2], 0))  # True

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

관련 문제에서는 특정 대상값을 찾지 않고 회전된 정렬 배열에서 최솟값을 찾습니다. 최솟값은 항상 정렬되지 않은 절반에 있습니다. 각 단계에서는 다음과 같이 합니다. arr[mid] > arr[hi]이면 최솟값이 오른쪽 절반에 있으므로(lo = mid + 1), 그렇지 않으면 mid를 포함한 왼쪽 절반에 있으므로(hi = mid) 범위를 그쪽으로 좁힙니다. lo == hi가 되면 최솟값을 찾은 것입니다.

def find_min(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1   # min is in right half
        else:
            hi = mid       # min is at mid or left of mid
    return nums[lo]

print(find_min([3, 4, 5, 1, 2]))   # 1
print(find_min([4, 5, 6, 7, 0, 1, 2]))  # 0
print(find_min([11, 13, 15, 17]))  # 11 (no rotation)

arr[lo] <= arr[mid]가 정렬된 왼쪽 절반을 감지하는 이유

arr[lo] <= arr[mid] 조건이 작동하는 이유는 정렬된(또는 회전되지 않은) 구간에서는 첫 번째 요소가 항상 가장 작기 때문입니다. arr[lo] <= arr[mid]이면 [lo..mid] 안에서는 회전이 발생하지 않았으므로 해당 절반이 정렬되어 있습니다. lo == mid인 경우도 처리할 수 있는데, 요소 하나로 이루어진 구간은 당연히 정렬되어 있기 때문입니다.

반대로 arr[lo] > arr[mid]이면 회전 피벗이 lo와 mid 사이에 있어야 하므로, 오른쪽 절반 [mid..hi]이 연속된 정렬 구간입니다.

# Visualise: detect which half is sorted
examples = [
    ([4, 5, 6, 7, 0, 1, 2], 0, 6),  # mid=3, val=7 => left sorted
    ([6, 7, 0, 1, 2, 4, 5], 0, 6),  # mid=3, val=1 => right sorted
]
for arr, lo, hi in examples:
    mid = lo + (hi - lo) // 2
    if arr[lo] <= arr[mid]:
        print(f'arr[{lo}]={arr[lo]} <= arr[{mid}]={arr[mid]}  => LEFT half sorted')
    else:
        print(f'arr[{lo}]={arr[lo]} >  arr[{mid}]={arr[mid]}  => RIGHT half sorted')

복잡도 분석

회전된 정렬 배열을 이진 탐색으로 탐색해도 매 반복마다 탐색 공간을 절반으로 줄이므로 시간 복잡도는 O(log n), 공간 복잡도는 O(1)입니다. 고전적인 이진 탐색과의 유일한 차이는 어느 절반이 정렬되었는지 확인하는 상수 시간 검사가 추가된다는 점입니다.

중복값이 있으면 각 단계에서 lo를 1만 증가시킬 수도 있으므로 최악의 경우 시간 복잡도가 O(n)으로 늘어납니다. 이러한 절충을 명시적으로 언급하면 정상적인 경우를 넘어 경계 사례까지 고려하고 있음을 보여 줄 수 있습니다.

LeetCode 33 풀이

LeetCode 33의 '회전된 정렬 배열에서 탐색하기'는 이 문제의 대표적인 형태입니다. 제약 조건상 중복값이 없고 정확히 한 번 회전합니다. 해답은 앞에서 작성한 search_rotated 함수입니다. 면접에서 중요한 점은 다음과 같습니다. 중복값이 없다는 가정을 항상 명시하고, 경계에 있는 구체적인 예로 부등식을 확인하며, 값을 찾은 경우와 찾지 못한 경우 모두 반환된 인덱스가 올바른지 확인해야 합니다.

# LeetCode 33 — complete solution
def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] == target:
            return mid
        if nums[lo] <= nums[mid]:        # left half sorted
            if nums[lo] <= target < nums[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                            # right half sorted
            if nums[mid] < target <= nums[hi]:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

# Tests
print(search([4,5,6,7,0,1,2], 0))   # 4
print(search([4,5,6,7,0,1,2], 3))   # -1
print(search([1], 0))               # -1

LeetCode 153: 중복 없는 최솟값 찾기

LeetCode 153의 '회전된 정렬 배열에서 최솟값 찾기'는 중복값 없이 최솟값을 찾는 문제입니다. 접근 방법은 arr[lo]가 아니라 arr[mid]를 arr[hi]와 비교하여 최솟값이 어느 쪽에 있는지 판단하는 것입니다. arr[mid] > arr[hi]이면 최솟값은 오른쪽에 있고, 그렇지 않으면 mid 또는 그 왼쪽에 있습니다. 이 방법은 O(log n)에 최솟값으로 수렴합니다.

def findMin(nums):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    return nums[lo]

print(findMin([3,4,5,1,2]))         # 1
print(findMin([4,5,6,7,0,1,2]))     # 0
print(findMin([11,13,15,17]))       # 11

회전 횟수와 피벗 인덱스

최솟값을 찾을 수 있다면 회전 횟수도 알 수 있습니다. 최솟값의 인덱스가 배열을 오른쪽으로 회전한 횟수와 정확히 같습니다. 예를 들어 [4,5,6,7,0,1,2]에서는 최솟값이 인덱스 4에 있으므로 배열을 4칸 회전한 것입니다.

피벗을 알면 인덱스를 n으로 나눈 나머지를 사용하여 표준 이진 탐색을 적용할 수 있습니다. real_idx = (mid + pivot) % n과 같이 표현합니다. 이 대안적인 방식은 순환 인덱스 구조를 다룰 때 추론을 단순하게 만들 수 있습니다.

def search_via_pivot(nums, target):
    n = len(nums)
    # Find pivot (index of minimum)
    lo, hi = 0, n - 1
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if nums[mid] > nums[hi]:
            lo = mid + 1
        else:
            hi = mid
    pivot = lo
    # Binary search with offset
    lo, hi = 0, n - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        real_mid = (mid + pivot) % n
        if nums[real_mid] == target:
            return real_mid
        elif nums[real_mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(search_via_pivot([4,5,6,7,0,1,2], 0))  # 4

모두 종합하기

면접에서 회전된 배열 문제를 만나면 다음 결정 트리를 따르십시오. 먼저 대상값을 찾아야 하는지, 아니면 최솟값을 찾아야 하는지 판단합니다. 대상값을 찾을 때는 정렬된 절반 식별 방식을 사용합니다. 최솟값을 찾을 때는 mid를 hi와 비교합니다. 중복값이 있을 수 있다면 최악의 경우가 O(n)임을 언급하고 경계를 줄이는 대안을 추가하십시오.

회전하지 않은 경우, 한 번 회전한 경우, 최솟값이 마지막 위치에 오도록 회전한 경우라는 세 가지 대표 예제에서 코드를 따라가며 연습해 보십시오.

빠른 확인

이 레슨에서 배운 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보십시오.

레슨 요약

이 레슨에서는 다음을 배웠습니다. 회전된 정렬 배열에는 항상 하나 이상의 정렬된 절반이 있습니다. 탐색할 위치를 결정하기 전에 arr[lo]와 arr[mid]를 비교하여 어느 절반이 정렬되었는지 식별합니다. 또한 최솟값을 찾을 때는 arr[mid]와 arr[hi]를 비교하여 회전 피벗을 찾습니다. 다음으로 하한 및 상한 이진 탐색 변형을 살펴봅니다.

자주 묻는 질문

“회전 배열과 정렬되지 않은 배열의 이진 검색” 강의는 무료인가요?

네 — “회전 배열과 정렬되지 않은 배열의 이진 검색” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“회전 배열과 정렬되지 않은 배열의 이진 검색”에서 뭘 배우나요?

각 단계에서 어느 절반이 정렬되어 있는지 판단해 search-in-rotated-sorted-array와 find-minimum-in-rotated-array를 해결합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.

“회전 배열과 정렬되지 않은 배열의 이진 검색” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. 고전적인 이진 검색: 왼쪽, 오른쪽, 중간
  2. 회전 배열과 정렬되지 않은 배열의 이진 검색
  3. 하한과 상한
  4. 답 공간 이진 검색
← DSA Interview Prep(으)로 돌아가기