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-
nums의 모든 값은 서로 다릅니다. nums는 어떤k만큼 회전된 오름차순 리스트이며,0 ≤ k < nums.length입니다.k = 0이면 회전되지 않은 상태로 유지됩니다.
예제
- 입력
- nums = [15, 19, 23, 2, 5, 8, 11]target = 5
- 출력
- 4
- 설명
- 첫 번째 중간값인 인덱스 3에는 2가 들어 있으므로, 오른쪽 절반
[2, 5, 8, 11]은 정렬되어 있고 5를 포함합니다. 다음 중간값인 인덱스 5에는 8이 들어 있습니다. 정렬된 왼쪽 부분[5, 8]에는 5가 있으므로 인덱스 4로 이어집니다.
- 입력
- nums = [40, 50, 60, 70, 10, 20, 30]target = 65
- 출력
- -1
- 설명
- 65는 60과 70 사이에 있어야 하지만, 어떤 요소도 이를 보유하지 않습니다. 첫 번째 중간값인 70으로 인해 65는 정렬된 왼쪽 부분
[40, 50, 60, 70]안에 위치하고, 범위는 그곳에서 비어 있을 때까지 줄어듭니다.
- 입력
- nums = [8, 13, 21, 1, 3, 5]target = 13
- 출력
- 1
- 설명
- 첫 번째 중간값인 인덱스 2에는 21이 있습니다. 왼쪽 부분
[8, 13, 21]은 정렬되어 있고 13은 8과 21 사이에 있으므로 오른쪽 부분은 버립니다. 그러면 검색을 통해 인덱스 1에서 13을 찾습니다.
후속 질문
nums에 중복된 값이 있을 수 있다면, 어떤 알고리즘도 O(log n)을 보장할 수 없습니다. 단 하나의 0을 숨긴 1로 이루어진 회전된 리스트를 사용해 이를 증명할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
중간 인덱스를 아무거나 하나 선택하고 그 양쪽에 있는 두 부분을 살펴보세요. 회전으로 인해 값이 가장 큰 값에서 가장 작은 값으로 내려가는 지점이 한 곳 생겼습니다. 두 부분 모두 그 하락 지점을 포함할 수 있을까요?
항상 적어도 한쪽 절반은 정렬되어 있으며,
nums[lo]와nums[mid]를 비교하면 어느 쪽인지 알 수 있습니다. 정렬된 절반에서는 한 번의 확인으로target이 첫 번째 값과 마지막 값 사이에 있는지 확인할 수 있습니다.target가 여전히 있을 수 있는 부분을lo와hi로 계속 좁혀 나가세요. 각 단계에서 정렬된 절반의 값 범위에target이 포함되면 그 절반을 유지하고, 그렇지 않으면 다른 절반을 유지하세요.target을 찾거나 범위가 비어 있으면 멈추세요.
풀이
회전된 정렬 리스트는 정렬된 두 구간, 즉 [15, 19, 23] 다음에 [2, 5, 8, 11]로 이루어져 있습니다. target과 중간 값을 비교해도 어느 쪽에 target이 있는지 더는 알 수 없습니다. 하지만 리스트를 어디에서 나누든 적어도 한쪽 절반은 정렬되어 있고, 한 번 비교하면 target이 그 절반에 있을 수 있는지 알 수 있습니다.
모든 요소를 스캔합니다
핵심 아이디어
모든 인덱스를 확인하고 값이 target과 같은 첫 번째 인덱스를 반환하거나, 루프가 끝난 후 -1을 반환합니다. 모든 요소를 읽으므로 어떤 리스트에서도 올바르게 동작합니다. 정렬된 두 구간을 활용하지 않습니다. 요소가 5000개라면 비교가 최대 5000번 필요하지만, 이진 탐색은 13번이면 됩니다.
알고리즘
- 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라고 하겠습니다. nums[k..n-1]과 nums[0..k-1]은 모두 정렬되어 있으며, 첫 번째 구간의 모든 값은 두 번째 구간의 모든 값보다 큽니다. k를 알고 나면 target을 nums[k] 및 nums[n-1]과 비교해 어느 구간에 있는지 고르고, 일반적인 이진 탐색을 수행하면 됩니다.
k를 찾으려면 가운데 값과 nums[hi]를 비교합니다. nums[mid] > nums[hi]이면 mid 다음 어딘가에서 값이 떨어지므로 최솟값은 오른쪽에 있습니다. 그렇지 않으면 nums[mid..hi]는 떨어지는 지점 없이 증가하므로 최솟값은 mid 또는 그 왼쪽에 있습니다. 첫 번째 예에서 가운데 값은 2, 19, 23이며, 따라서 k = 3이고 5는 nums[3] = 2와 nums[6] = 11 사이에 있습니다. 이진 탐색 두 번에는 약 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까지 탐색합니다.- 찾은 인덱스를 반환하거나, 범위가 비면
-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를 기준으로 한 두 절반 중 많아야 하나에만 값이 떨어지는 지점이 있고, 다른 절반은 정렬되어 있습니다. nums[lo] ≤ nums[mid]이면 왼쪽 절반이 정렬되어 있고, 그렇지 않으면 오른쪽 절반이 정렬되어 있습니다.
정렬된 절반에서는 양 끝의 범위를 검사하면 target이 그 안에 있을 수 있는지 알 수 있습니다. 예를 들어 왼쪽 절반에서는 nums[lo] ≤ target < nums[mid]입니다. 그 안에 있을 수 있다면 해당 절반에서 탐색하고, 그렇지 않다면 target은 다른 절반에만 있을 수 있습니다. 각 단계에서 범위가 절반으로 줄어듭니다. 원소가 5000개라면 최대 13단계입니다.
알고리즘
lo = 0과hi = n-1을 설정합니다.lo ≤ hi인 동안mid를 계산하고,nums[mid]가target과 같으면 이를 반환합니다.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이면-1을 반환합니다.target을nums[mid]와 먼저 비교하는 경우.target = 19인 첫 번째 예시에서는 중간값 2가 더 작으므로 검색이 오른쪽으로 이동해 인덱스 1을 놓칩니다.- 정렬된 절반의 한쪽 끝만 검사하는 경우.
[40, 50, 60, 70, 80, 10, 20]에서target = 80일 때target ≥ nums[lo]만 검사하면 검색이[40, 50, 60, 70]으로 이동합니다. - Rust에서는 회전되지 않은 목록인
k = 0일 때usize의k - 1연산에서 언더플로가 발생합니다. 반열린 범위를 사용하세요. - Lua와 R에서는 1부터 시작하는 위치를 반환합니다. 1을 빼세요.
자주 묻는 질문3
회전된 정렬 배열을 검색하는 시간 복잡도는 얼마인가요?
O(log n) 시간과 O(1) 추가 공간. 각 단계에서 범위의 절반을 유지하므로 요소가 5000개라면 최대 13단계가 필요합니다. 회전 지점을 먼저 찾는 작업도 O(log n)이며, 단계 수는 약 두 배입니다.
배열에 중복 항목이 있어도 알고리즘이 작동하나요?
작성된 그대로는 아닙니다. nums[lo], nums[mid], nums[hi]가 같으면 어느 쪽 절반이 정렬되어 있는지 증명할 수 없습니다. 일반적인 해결 방법은 이 경우 lo를 1만큼 앞으로 이동하는 것입니다. 이렇게 하면 정답은 올바르게 유지되지만 최악의 경우 O(n)이 됩니다.
회전 지점을 먼저 찾을까요, 아니면 한 번에 검색할까요?
둘 다 O(log n)으로 실행됩니다. 먼저 최솟값을 찾으면 문제가 두 번의 일반 이진 탐색으로 나뉩니다. 한 번에 탐색하는 방식은 더 적은 단계로 단일 루프에서 작업을 수행하며, 대부분의 면접관이 기대하는 방식입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def search(nums, target):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자들
nums = [15, 19, 23, 2, 5, 8, 11] target = 5
예상 출력
4