Search in Rotated Sorted Array
서로 다른 정수로 이루어진 목록을 오름차순으로 정렬한 다음 회전했습니다. 즉, 맨 앞에서 0개 이상의 원소를 가져와 같은 순서로 맨 뒤로 옮겼습니다. 예를 들어, [2, 5, 8, 11, 15, 19, 23]을 4만큼 회전하면 [15, 19, 23, 2, 5, 8, 11]이 됩니다. 회전된 목록 nums와 정수 target이 주어집니다. target이 nums에 있으면 0부터 세는 인덱스를 반환하고, 없으면 -1을 O(log n) 시간에 반환하세요.
함수
- numsinteger-array
- 회전된 정렬된 고유 정수 목록
- targetinteger
- 찾을 값
- 반환값integer
- nums에서 target의 인덱스, 또는 찾을 수 없으면 -1
제약 조건
1 ≤ nums.length ≤ 5000-104 ≤ nums[i], target ≤ 104- < no? exact format tags, content. Avoid leading space.
nums는0 ≤ k < nums.length인 어떤k만큼 회전된 오름차순 리스트이며,k = 0이면 회전되지 않습니다.
예제
- 입력
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- 출력
- 4
- 설명
- 5는 인덱스 4에 있습니다. 첫 번째 중간값인 인덱스 3에는 2가 있으므로, 오른쪽 절반
[2, 5, 8, 11]이 정렬되어 있고 5는 2와 11 사이에 있습니다. 다음 중간값인 인덱스 5에는 8이 있습니다. 정렬된 왼쪽 부분[5, 8]에는 5가 있으므로 인덱스 4로 이어집니다.
- 입력
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- 출력
- -1
- 설명
- 65는 60과 70 사이에 위치하며, 어떤 요소도 이를 담고 있지 않습니다. 첫 번째 중간값인 인덱스 3의 70은 65가 정렬된 왼쪽 부분
[40, 50, 60, 70]안에 있음을 보여 줍니다. 범위가 그 구간 안에서 좁아지다가 비게 되므로 함수는-1을 반환합니다.
- 입력
- nums = [8, 13, 21, 1, 3, 5]target = 13
- 출력
- 1
- 설명
- 첫 번째 중간값인 인덱스 2에는 21이 있습니다. 왼쪽 부분
[8, 13, 21]은 정렬되어 있고 13은 8과 21 사이에 있으므로, 오른쪽 부분 전체를 버립니다. 그런 다음 검색을 통해 인덱스 1에서 13을 찾습니다.
제출 시 숨은 테스트 +23개
후속 질문
nums에 중복 항목이 있을 수 있다면, 어떤 알고리즘도 O(log n)을 보장할 수 없습니다. 이를 증명할 수 있나요? 1로 이루어진 회전된 리스트에 0 하나를 숨겨 넣어, 0을 찾으려면 모든 요소를 읽어야 하는 상황을 만들어 보세요.
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
중간 인덱스 하나를 선택하고 그 양쪽의 두 구간을 살펴보세요. 회전으로 인해 값이 가장 큰 값에서 가장 작은 값으로 내려가는 지점이 하나 생겼습니다. 두 구간 모두에 그 하강 지점이 있을 수 있을까요?
항상 적어도 절반은 정렬되어 있으며,
nums[lo]와nums[mid]를 비교하면 어느 쪽인지 알 수 있습니다. 정렬된 절반에서는target이 첫 번째 값과 마지막 값 사이에 있는지 한 번의 단계로 확인할 수 있습니다.lo와hi는target이 여전히 들어 있을 수 있는 부분을 둘러싸도록 유지하세요. 각 단계에서 정렬된 절반의 값 범위에target이 포함되면 그 절반을 유지하고, 그렇지 않으면 다른 절반을 유지하세요.target을 찾거나 범위가 비게 되면 중단하세요.
풀이
회전된 정렬 리스트는 정렬된 두 구간이 차례로 이어진 것입니다. [15, 19, 23] 다음에 [2, 5, 8, 11]이 오는 식입니다. 일반 이진 탐색은 이 리스트에서 제대로 작동하지 않습니다. 가운데 값과 target을 비교해도 target이 어느 쪽에 있는지 더 이상 알 수 없기 때문입니다. 해결책은 한 가지 사실에 있습니다. 리스트를 어디에서 나누든 두 절반 중 적어도 하나는 완전히 정렬되어 있으며, 정렬된 절반에서는 한 번의 비교로 target이 그 안에 있을 수 있는지 알 수 있습니다.
모든 요소를 스캔합니다
핵심 아이디어
각 인덱스를 순서대로 확인하고, 값이 target과 같은 첫 번째 인덱스를 반환합니다. 일치하는 항목 없이 반복문이 끝나면 -1을 반환합니다. 값은 서로 다르므로 첫 번째 일치 항목이 유일하며, 회전 여부와 관계없이 어떤 리스트에서도 이 탐색은 올바릅니다.
문제에서 알려 준 내용을 모두 무시합니다. 리스트는 정렬된 두 구간으로 이루어져 있지만, 이 탐색은 최대 5000개의 모든 요소를 읽습니다. 반면 이진 탐색에는 약 13번의 비교가 필요합니다. 입력이 커질수록 차이는 커집니다. 요소가 백만 개면 비교가 백만 번 필요한 반면, 이진 탐색은 약 20번이면 됩니다. 문제에서는 O(log n)을 요구하므로, 이것은 개선해야 할 기준이지 정답이 아닙니다.
알고리즘
- 0부터
n-1까지 각 인덱스i에 대해nums[i]와target을 비교합니다. - 두 값이 같으면
i를 반환합니다. - 반복문이 끝난 후
-1을 반환합니다.
def search(nums, target):
for i, value in enumerate(nums):
if value == target:
return i
return -1회전 지점을 찾은 다음 이진 탐색하기
핵심 아이디어
회전된 리스트는 정렬된 두 구간으로 이루어져 있으며, 두 번째 구간은 가장 작은 값에서 시작합니다. 그 인덱스를 k라고 합시다. k를 알면 문제는 일반적인 이진 탐색으로 바뀝니다. nums[k..n-1]은 정렬되어 있고 nums[k]부터 nums[n-1]까지의 값을 포함하며, nums[0..k-1]은 정렬되어 있고 그보다 큰 모든 값을 포함합니다. target을 nums[k] 및 nums[n-1]과 한 번 비교하면 탐색할 구간을 선택할 수 있습니다.
k를 찾으려면 값이 떨어지는 지점을 이진 탐색합니다. 중간값을 범위의 마지막 값인 nums[hi]와 비교합니다. nums[mid] > nums[hi]이면 mid 뒤쪽 어딘가에서 값이 감소하므로 가장 작은 값은 그 오른쪽에 있습니다. 따라서 lo = mid + 1로 설정합니다. 그렇지 않으면 nums[mid..hi]는 감소하는 지점 없이 증가하므로 가장 작은 값은 mid이거나 그 앞에 있습니다. 따라서 mid를 범위에 포함하도록 hi = mid로 설정합니다. lo와 hi가 같아지면 그 인덱스가 k입니다.
첫 번째 예시인 [15, 19, 23, 2, 5, 8, 11]에서 target = 5인 경우를 추적해 봅시다. 중간값 2는 11보다 크지 않으므로 hi는 3이 됩니다. 그런 다음 19는 2보다 크므로 lo는 2가 됩니다. 이어서 23은 2보다 크므로 lo는 3이 되고, k = 3입니다. 5는 nums[3] = 2와 nums[6] = 11 사이에 있으므로 인덱스 3부터 6까지 탐색하면 이진 탐색으로 인덱스 4에서 5를 찾습니다. 이진 탐색 두 번에는 약 2 log2 n 단계가 걸립니다.
알고리즘
lo = 0및hi = n-1로 설정합니다.lo < hi인 동안mid를 계산합니다.nums[mid] > nums[hi]이면lo = mid + 1로 설정하고, 그렇지 않으면hi = mid로 설정합니다.- 최종 인덱스를
k라고 합니다. 이 인덱스에는 가장 작은 값이 있습니다. nums[k] ≤ target ≤ nums[n-1]이면 인덱스k부터n-1까지 검색하고, 그렇지 않으면 인덱스 0부터k-1까지 검색합니다.- 해당 범위에서 일반 이진 검색을 수행하고
target의 인덱스를 반환합니다. 범위가 비면-1을 반환합니다.
def search(nums, target):
n = len(nums)
# 1. Find k, the index of the smallest value, where the second run starts.
lo, hi = 0, n - 1
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # the drop is right of mid
else:
hi = mid # mid is in the low run: the minimum is at mid or left of it
k = lo
# 2. nums[k..n-1] and nums[0..k-1] are sorted: search the one whose range holds target.
if nums[k] <= target <= nums[n - 1]:
lo, hi = k, n - 1
else:
lo, hi = 0, k - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1정렬된 절반에서의 이진 탐색 한 번
핵심 아이디어
회전 지점이 어디인지 알 필요는 없습니다. 이진 탐색의 일반적인 약속을 유지하세요. target이 목록에 있다면 그 인덱스는 lo와 hi 사이에 있습니다. 가운데 인덱스 mid를 살펴보세요. 전체 목록에서 값은 한 번만 감소하므로, 그 감소 지점은 mid를 기준으로 한 두 절반 중 최대 하나에만 있고 다른 절반은 정렬되어 있습니다.
비교 한 번으로 정렬된 절반을 찾으세요. nums[lo] ≤ nums[mid]이면 왼쪽 절반 nums[lo..mid]에는 감소 지점이 없고 정렬되어 있습니다. 이미 nums[mid]가 target이 아니라는 것을 알고 있으므로, target은 nums[lo] ≤ target < nums[mid]인 경우에만 그 절반에 있을 수 있습니다. 그렇다면 hi = mid - 1로 설정하세요. 그렇지 않으면 target은 다른 절반에만 있을 수 있으므로 lo = mid + 1로 설정하세요. nums[lo] > nums[mid]일 때는 감소 지점이 왼쪽에 있고 오른쪽 절반 nums[mid..hi]가 정렬되어 있으며, 반대 조건인 nums[mid] < target ≤ nums[hi]으로 판단합니다. 정렬되지 않은 절반을 직접 따져 볼 필요는 없습니다. 정렬된 절반에 target이 없을 때에만 그 절반을 탐색하게 됩니다.
첫 번째 예시인 [15, 19, 23, 2, 5, 8, 11]에서 target = 5인 경우를 따라가 보세요. 범위가 0부터 6까지이고 가운데 인덱스는 3, 값은 2입니다. 15가 2보다 크므로 오른쪽 절반 [2, 5, 8, 11]이 정렬되어 있고, 그 안에 5가 있으므로 lo는 4가 됩니다. 범위가 4부터 6까지이고 가운데 인덱스는 5, 값은 8입니다. 이제 nums[4] = 5 ≤ 8이므로 왼쪽 절반 [5, 8]은 정렬되어 있고 5를 포함하므로 hi는 4가 됩니다. 인덱스 4에 5가 있으므로 4를 반환합니다.
일반 이진 탐색과 마찬가지로 매 단계마다 범위가 절반으로 줄어드므로, 반복문은 최대 약 log2(n) + 1회 실행됩니다. 요소가 5000개일 때 13단계이며, 추가 메모리는 인덱스 두 개뿐입니다.
알고리즘
lo = 0과hi = n-1을 설정합니다.lo ≤ hi인 동안mid를 계산합니다.nums[mid]가target과 같으면mid를 반환합니다.nums[lo] ≤ nums[mid]이면 왼쪽 절반이 정렬되어 있습니다.nums[lo] ≤ target < nums[mid]이면hi = mid - 1을 설정하고, 그렇지 않으면lo = mid + 1을 설정합니다.- 그렇지 않으면 오른쪽 절반이 정렬되어 있습니다.
nums[mid] < target ≤ nums[hi]이면lo = mid + 1을 설정하고, 그렇지 않으면hi = mid - 1을 설정합니다. - 반복문이 끝나면
-1을 반환합니다.
def search(nums, target):
lo, hi = 0, len(nums) - 1 # target, if present, sits in nums[lo..hi]
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]:
# nums[lo..mid] is sorted: target is in it only if it fits its range
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
# nums[mid..hi] is sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
함정과 경계 사례
한 번의 탐색은 짧고, 거의 모든 버그는 비교 연산자에서 발생합니다.
nums[lo] < nums[mid]처럼 쓰고≤를 사용하지 않는 경우입니다. 원소가 두 개 남으면mid는lo와 같고, 왼쪽 절반은 정렬된 원소 하나입니다. 엄격한 조건을 사용하면[9, 4]와target = 4에서[9, 4]를 정렬된 오른쪽 절반으로 취급하고, 9부터 4까지의 범위 밖에서 4를 찾으려 하므로-1을 반환합니다.- 일반 이진 탐색처럼 먼저
target을nums[mid]와 비교하는 경우입니다.[15, 19, 23, 2, 5, 8, 11]에서target = 19이면 중간값 2는 19보다 작으므로 탐색은 오른쪽으로 이동하고 인덱스 1을 확인하지 않습니다. - 정렬된 절반의 한쪽 끝만 확인하는 경우입니다.
[40, 50, 60, 70, 80, 10, 20]에서target = 80이면 중간값은 70이고 왼쪽 절반인[40, 50, 60, 70]은 정렬되어 있습니다.target ≥ nums[lo]만 확인하면 80이 40보다 크기 때문에 탐색이 왼쪽으로 이동하지만, 80은 70보다도 크므로 오른쪽 절반에 있습니다. 양쪽 끝을 모두 확인하세요. - 두 단계 접근 방식에서 회전되지 않은 경우를 잊는 것입니다.
k = 0이면 두 번째 탐색은 비어 있고 범위는0부터-1까지입니다. 부호 있는 인덱스에서는 괜찮지만, 부호 없는 인덱스(Rust의usize)에서는k - 1이 언더플로되므로 Rust 코드는 반개방 범위를 사용합니다. - Lua와 R에서 위치 자체를 반환하는 경우입니다. 이 언어들의 리스트는 1부터 시작하므로 반환하기 전에 1을 빼세요.
자주 묻는 질문4
회전된 정렬 배열을 검색하는 시간 복잡도는 얼마인가요?
O(log n) 시간과 O(1) 추가 공간이 필요합니다. 각 단계에서 현재 범위의 절반만 남기므로 일반 이진 검색과 같으며, 따라서 원소가 5000개인 목록도 최대 13단계면 됩니다. 회전 지점을 먼저 찾는 두 단계 버전도 O(log n)이며, 단계 수는 약 두 배입니다.
회전된 배열의 어느 절반이 정렬되어 있는지 어떻게 알 수 있나요?
nums[lo]와 nums[mid]를 비교합니다. 전체 목록에서 값은 한 번만 내려갑니다. nums[lo] ≤ nums[mid]이면 그 하락은 lo와 mid 사이에 없으므로 왼쪽 절반은 정렬되어 있습니다. 그렇지 않으면 하락은 왼쪽 절반에 있으므로, mid부터 hi까지의 오른쪽 절반에는 하락이 없으며 정렬되어 있습니다.
배열에 중복 항목이 포함되어 있어도 알고리즘이 작동하나요?
현재 작성된 방식으로는 그렇지 않습니다. [1, 0, 1, 1, 1]에서 nums[lo], nums[mid] 및 nums[hi]는 모두 1이므로, 어느 쪽 절반도 정렬되어 있다고 증명할 수 없습니다. 일반적인 해결 방법은 nums[lo], nums[mid] 및 nums[hi]가 같을 때 lo를 1 증가시키는 것입니다. 이렇게 하면 답의 정확성은 유지되지만 최악의 경우 시간 복잡도는 O(n)이 됩니다.
먼저 회전 지점을 찾아야 할까요, 아니면 한 번에 검색해야 할까요?
둘 다 O(log n)으로 실행됩니다. 최솟값의 인덱스를 찾으면 문제가 두 개의 일반 이진 탐색으로 나뉘므로, 각 부분에서 이미 신뢰할 수 있는 코드를 재사용할 수 있습니다. 한 번에 탐색하는 방법은 한 번의 루프에서 더 적은 단계로 같은 작업을 수행하며, 면접관들이 가장 기대하는 방식입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def search(nums, target):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
기대값
4