Find First and Last Position of Element in Sorted Array
정수가 비내림차순으로 정렬된 목록 nums와 정수 target이 주어집니다. 따라서 값이 반복될 수 있습니다. 0부터 세는 두 인덱스의 목록, 즉 target이 나타나는 첫 번째 위치와 마지막 위치를 반환하세요. target이 목록에 없으면 [-1, -1]을 반환하세요. 시간 복잡도는 O(log n)을 목표로 하세요.
함수
- numsinteger-array
- 값이 반복될 수 있는 정렬된 정수 목록
- targetinteger
- 찾을 값
- 반환값integer-array
- target의 첫 번째 인덱스와 마지막 인덱스, 또는 target이 없으면 [-1, -1]
제약 조건
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104nums는 비내림차순으로 정렬되어 있습니다.
예제
- 입력
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- 출력
- [1, 3]
- 설명
- 5의 세 복사본은 인덱스 1, 2, 3에 있으므로, 연속 구간은 1에서 시작해 3에서 끝납니다. 인덱스 0에는 3이 있고 인덱스 4에는 8이 있으므로, 연속 구간은 더 이어질 수 없습니다.
- 입력
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- 출력
- [-1, -1]
- 설명
- 7은 인덱스 3의 5와 인덱스 4의 8 사이에 위치하며, 어느 쪽도 7이 아닙니다. 목록에 7이 없으므로 답은
[-1, -1]입니다.
후속 질문
같은 리스트에 대해 서로 다른 대상을 찾는 쿼리가 수천 번 들어온다면, 미리 한 번 순회하는 것만으로 각 쿼리를 O(log n)보다 빠르게 처리할 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
nums는 정렬되어 있으므로target의 모든 복사본은 하나의 연속 구간에 나란히 모여 있습니다. 이 구간의 양 끝을 찾아야 합니다.하나의 사본을 찾은 뒤 바깥쪽으로 탐색하면 구간이 길 때
O(n)의 비용이 들 수 있습니다. 대신 일치 항목을 찾은 뒤에도 왼쪽으로 계속 탐색하도록 이진 검색을 변경하세요. 그러면 찾는 숫자 이상의 값이 있는 첫 번째 인덱스에서 멈춥니다.nums[i] ≥ value를 만족하는 첫 번째 인덱스를 반환하는 헬퍼를 하나 작성하세요.target을 전달해 연속 구간의 시작을 구하고, 해당 위치의 값이target인지 확인한 다음,target + 1을 전달해 호출하세요. 연속 구간은 그 인덱스보다 하나 앞에서 끝납니다.
풀이
일반적인 이진 탐색은 target의 어느 복사본을 만나든 그 지점에서 멈추며, 그 복사본은 연속 구간 어디에나 있을 수 있습니다. 대신 하한을 찾으세요. 하한은 주어진 숫자보다 크거나 같은 값을 가진 첫 번째 인덱스입니다. target과 target + 1의 하한을 구하면 O(log n)에 연속 구간의 양 끝을 모두 알 수 있습니다.
목록 전체를 훑어보세요
핵심 아이디어
목록을 한 번 훑습니다. target이 있는 첫 번째 인덱스가 시작이고 마지막 인덱스가 끝입니다. target이 나타나지 않으면 둘 다 -1로 남습니다.
이 방법은 정렬 여부와 관계없이 모든 목록에서 작동하며, 그것이 단점입니다. n개의 값을 모두 읽기 때문입니다. 10^4개의 값이 있는 목록은 비교 약 28회면 충분한 작업에 비교 10,000회가 듭니다.
알고리즘
first = last = -1로 설정합니다.- 각 인덱스
i에 대해nums[i]가target과 같으면,first가 여전히-1일 때first = i로 설정하고last = i로 설정합니다. [first, last]를 반환합니다.
def searchRange(nums, target):
first = last = -1
for i, value in enumerate(nums):
if value == target:
if first == -1:
first = i # the first match fixes the start
last = i # every later match moves the end
return [first, last]사본 하나를 찾은 다음 확장합니다
핵심 아이디어
target가 있는 임의의 인덱스를 이진 검색합니다. 리스트가 정렬되어 있으므로, 같은 값은 해당 인덱스 주변의 끊김 없는 구간에 모여 있습니다. 이웃한 값이 여전히 target인 동안 왼쪽과 오른쪽으로 이동합니다.
검색에는 O(log n)이 걸리고, 모든 복사본을 훑는 데는 복사본당 한 걸음씩, 총 k걸음이 걸립니다. 리스트 대부분이 target인 경우, 예를 들어 10^4개의 복사본이 있으면, 훑는 과정에서 모든 값을 읽게 되어 선형 검색을 하는 것과 같아집니다.
알고리즘
nums[found] == target인found인덱스를 이진 탐색합니다.- 찾지 못하면
[-1, -1]을 반환합니다. first앞의 값이target과 같은 동안found에서 왼쪽으로first를 이동합니다.last뒤의 값이target과 같은 동안found에서 오른쪽으로last를 이동합니다.[first, last]를 반환합니다.
def searchRange(nums, target):
# An ordinary binary search finds some copy of target, if there is one.
lo, hi = 0, len(nums) - 1
found = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
if found == -1:
return [-1, -1]
# The copies sit next to each other, so walk out to both ends of the run.
first = last = found
while first > 0 and nums[first - 1] == target:
first -= 1
while last < len(nums) - 1 and nums[last + 1] == target:
last += 1
return [first, last]두 개의 하한 이진 탐색
핵심 아이디어
다른 질문을 해 봅시다. 값이 value 이상인 첫 번째 인덱스는 무엇일까요? 그 인덱스가 하한이며, 해당하는 값이 없으면 n입니다. 항상 하한을 포함하는 반개구간 [lo, hi)을 유지합니다. nums[mid] < value이면 mid와 그 앞의 모든 값은 너무 작습니다. 그렇지 않으면 mid는 조건을 만족하지만, 더 앞선 인덱스도 조건을 만족할 수 있으므로 새로운 hi로 설정해 mid를 범위에 남겨 둡니다. 일치하는 값을 찾아도 루프는 일찍 끝나지 않습니다.
target의 하한은 해당 값이 시작되는 위치입니다. 값은 정수이므로 target보다 큰 첫 번째 값은 target + 1의 하한에 있고, 해당 값의 연속 구간은 그 인덱스보다 하나 앞선 위치에서 끝납니다. 첫 번째 예에서 5의 하한은 1이고 6의 하한은 4이며, 그 위치에 8이 있습니다. 따라서 연속 구간은 [1, 3]입니다. 연속 구간의 길이와 관계없이 두 번의 탐색에는 10^4개의 값에 대해 약 28단계가 걸립니다.
알고리즘
lowerBound(value)를 작성합니다.lo = 0,hi = n에서 시작합니다.lo < hi인 동안nums[mid] < value이면lo = mid + 1로 설정하고, 그렇지 않으면hi = mid로 설정합니다.lo를 반환합니다.first = lowerBound(target)로 설정합니다.first == n이거나nums[first] != target이면[-1, -1]을 반환합니다.last = lowerBound(target + 1) - 1로 설정하고[first, last]를 반환합니다.
def lowerBound(nums, value):
# The first index whose number is at least value, or len(nums) if none is.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < value:
lo = mid + 1 # nums[mid] and everything before it is too small
else:
hi = mid # nums[mid] qualifies, but an earlier index might too
return lo
def searchRange(nums, target):
first = lowerBound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
# The run of target ends right before the first number above target.
last = lowerBound(nums, target + 1) - 1
return [first, last]
함정과 경계 사례
nums[mid] == target인 즉시 반환하는 것. 해당 인덱스는 같은 값이 이어지는 구간의 어디에나 있을 수 있습니다.[3, 5, 5, 5, 8]에서 첫 번째 중간값의 인덱스는 2이며, 양 끝 어느 쪽도 아닙니다.nums[mid] ≥ value일 때 하한 검색에서hi = mid - 1을 작성하는 것. 이렇게 하면 정답일 수도 있는mid가 제외됩니다.first < n인지 확인하지 않고nums[first]를 읽는 것. 예시에서 13처럼target이 모든 값보다 큰 경우, 하한은 끝에서 한 칸 지난n입니다.- Lua와 R에서의 이동을 잊는 것. 이 언어들의 목록은 1부터 시작하므로 두 위치 모두에서 1을 빼세요.
자주 묻는 질문3
첫 번째 위치와 마지막 위치를 찾는 시간 복잡도는 얼마인가요?
두 번의 이진 탐색으로 시간은 O(log n), 공간은 O(1)입니다. 어느 탐색도 일치 항목을 찾았을 때 멈추지 않으므로 비용은 목표 값의 복사본이 몇 개 있는지에 좌우되지 않습니다. 10^4개의 값에 대해 탐색당 약 14단계입니다.
이진 검색에서 하한이란 무엇인가요?
값의 하한은 요소가 해당 값 이상인 첫 번째 인덱스이며, 그런 요소가 없으면 리스트의 길이입니다. 리스트의 정렬 상태를 유지하기 위해 해당 값을 삽입해야 하는 위치입니다. 상한은 요소가 해당 값보다 큰 첫 번째 인덱스입니다.
하나의 이진 검색 함수로 첫 번째 인덱스와 마지막 인덱스를 모두 찾을 수 있을까요?
네. 검색에 플래그를 추가하세요. 일치하는 항목을 찾으면 인덱스를 기록하고 첫 번째 항목을 찾기 위해 왼쪽으로 계속 검색하거나, 마지막 항목을 찾기 위해 오른쪽으로 계속 검색하면 됩니다. target과 target + 1에 대해 하한 검색을 호출해도 됩니다. 두 방법 모두 O(log n)의 시간이 걸립니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def searchRange(nums, target):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자들
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
예상 출력
[1, 3]