Binary Search

Q: 이진 검색의 시간 복잡도는 무엇인가요?

O(log n) . 각 비교는 대상이 있을 수 있는 범위를 절반으로 줄이므로, k 단계 후에는 최대 n / 2^k 개의 후보만 남습니다. 10^4 개의 요소가 있는 목록에는 비교가 최대 14회 필요하고, 10^9 개의 요소가 있는 목록에는 최대 30회 필요합니다. 반복 버전은 추가 공간을 O(1) 사용합니다.

Q: 이진 탐색에는 왜 정렬된 배열이 필요한가요?

목록의 절반을 버리는 단계는 순서에 의존합니다. nums[mid] < target 일 때, 정렬되어 있으면 mid 의 왼쪽에 있는 모든 요소도 target 보다 작다는 것이 보장되므로, 그중 일치하는 요소는 없습니다. 정렬되지 않은 목록에서는 이 비교만으로 다른 요소에 대해 아무것도 알 수 없으므로, 모든 요소를 확인해야 합니다.

Q: 이진 탐색은 반복문 방식이어야 할까요, 재귀 방식이어야 할까요?

둘 다 올바르며 O(log n) 시간에 실행됩니다. 재귀 버전은 한쪽 절반을 대상으로 자기 자신을 호출하고 O(log n) 의 스택 공간을 사용합니다. 반복 버전은 루프에서 lo 와 hi 를 이동하며 O(1) 을 사용합니다. 면접관은 보통 루프를 기대하며, 루프는 재귀 제한도 피할 수 있습니다.

Q: 중간 인덱스를 계산할 때 오버플로를 어떻게 방지하나요?

mid = lo + (hi - lo) / 2 를 (lo + hi) / 2 대신 사용하세요. 두 식은 같은 인덱스를 반환하지만, 두 번째 식은 먼저 두 인덱스를 더하므로 32비트 정수에서는 인덱스가 약 1.07 × 10^9 를 넘으면 합계가 오버플로됩니다. Python과 Ruby는 정수의 범위가 제한되지 않으므로, 이 언어들에서는 짧은 식도 안전합니다.

쉬움이진 탐색

+10

중복 값 없이 오름차순으로 정렬된 정수 목록 nums와 정수 target이 주어집니다. nums에서 target의 인덱스를 0부터 세어 반환하고, 목록에 없으면 -1을 반환하세요. O(log n) 시간 복잡도를 목표로 하세요. 이는 모든 요소를 살펴볼 수 없다는 뜻입니다.

함수

search(nums: integer-array, target: integer) → integer

numsinteger-array: 정렬된 고유한 정수 목록
targetinteger: 찾을 값
반환값integer: nums에서 target의 인덱스, 없으면 -1

제약 조건

1 ≤ nums.length ≤ 10⁴
-10⁴ ≤ nums[i], target ≤ 10⁴
nums는 엄격한 오름차순으로 정렬되어 있으므로 각 값은 한 번씩만 나타납니다.

예제

입력: nums = [-7, -2, 0, 4, 9, 15, 23]target = 9
출력: 4
설명: nums[4]는 9입니다. 검색은 인덱스 3(값 4, 너무 작음)을 살펴본 다음 인덱스 5(값 15, 너무 큼)를 살펴보고, 마지막으로 인덱스 4에서 9를 찾습니다.

입력: nums = [1, 3, 5, 8, 13, 21]target = 10
출력: -1
설명: 10은 8과 13 사이에 위치하며, 둘 다 10이 아니므로 목록에 없습니다. 검색 범위는 lo가 hi를 지나칠 때까지 줄어들고, 함수는 -1을 반환합니다.

제출 시 숨은 테스트 +15개

후속 질문

nums에 값이 반복될 수 있다면, 여전히 O(log n)으로 target의 첫 번째 인덱스를 어떻게 반환할 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

요소를 하나씩 읽으면 target을 찾을 수 있지만, 이 문제를 흥미롭게 만드는 한 가지 사실, 즉 목록이 정렬되어 있다는 점을 무시합니다. 가운데 요소와 한 번 비교하면 어느 쪽 절반에 target이 있을 수 있는지 알 수 있으므로, 매 단계마다 후보의 절반을 제외할 수 있습니다. 그러면 10^4개의 요소가 있는 목록을 10000번 비교하는 대신 최대 14번만 비교하면 됩니다.

왼쪽에서 오른쪽으로 스캔

핵심 아이디어

각 인덱스를 순서대로 확인하고, 값이 target과 같은 첫 번째 인덱스를 반환합니다. 일치하는 항목을 찾지 못한 채 루프가 끝나면 target은 목록에 없으므로 -1을 반환합니다. 모든 요소를 한 번씩 비교하므로 정렬 여부와 관계없이 어떤 목록에서도 정답을 구할 수 있습니다.

이러한 범용성이 문제입니다. 요소가 10^4개인 목록에서는 비교가 최대 10000번 필요하고, 작업량은 n에 비례해 증가합니다. 이 탐색은 nums가 정렬되어 있다는 사실을 전혀 활용하지 않으므로, 문제에서 요구하는 O(log n) 상한을 달성하지 못합니다. 값이 target보다 커지는 순간 일찍 멈출 수는 있지만, 최악의 경우에는 여전히 목록 전체를 읽어야 합니다.

알고리즘

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

두 인덱스를 사용한 이진 검색

핵심 아이디어

인덱스 lo와 hi 두 개를 유지하며, 다음 조건을 지킵니다. target이 리스트에 있다면 그 인덱스는 lo와 hi 사이에 있으며 양 끝값도 포함합니다. 처음에는 이 범위가 리스트 전체인 0부터 n-1까지입니다. 가운데 인덱스 mid를 확인합니다. nums[mid]가 target과 같으면 끝입니다. 더 작다면 리스트가 정렬되어 있으므로 mid까지의 모든 원소도 더 작습니다. 따라서 lo를 mid + 1로 옮깁니다. 더 크다면 hi를 mid - 1로 옮깁니다. 어느 쪽으로 옮겨도 조건은 계속 성립합니다.

첫 번째 예시인 target = 9인 [-7, -2, 0, 4, 9, 15, 23]을 추적해 봅시다. 0부터 6까지의 범위에서 가운데 인덱스는 3이고 값은 4입니다. 너무 작으므로 범위는 4부터 6까지가 됩니다. 가운데 인덱스 5의 값은 15로 너무 크므로 범위는 4부터 4까지가 됩니다. 인덱스 4의 값은 9입니다. 4를 반환합니다.

target이 없으면 lo가 hi를 넘어설 때까지 범위가 계속 줄어듭니다. 그러면 범위가 비게 되고, 조건에 따라 target이 어디에도 없으므로 -1을 반환합니다. 각 단계에서 범위가 절반으로 줄어들기 때문에 반복문은 최대 약 log2(n) + 1회 실행됩니다. 원소가 10^4개라면 14단계입니다. 추가로 필요한 메모리는 인덱스 두 개뿐입니다.

알고리즘

lo = 0과 hi = n-1을 설정합니다.
lo ≤ hi인 동안 mid = lo + (hi - lo) / 2를 계산합니다.
nums[mid]가 target과 같으면 mid를 반환합니다.
nums[mid] < target이면 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[mid] < target:
            lo = mid + 1  # nums[mid] and everything left of it is too small
        else:
            hi = mid - 1  # nums[mid] and everything right of it is too big
    return -1

함정과 경계 사례

이진 탐색은 짧고, 버그의 거의 대부분은 범위의 양 끝에서 발생하는 off-by-one 오류입니다.

hi가 마지막 인덱스에서 시작하는데 lo < hi 조건으로 반복하는 경우. 후보 하나를 확인하지 않은 채 반복이 끝나므로 nums = [5]이고 target = 5이면 -1을 반환합니다. 양 끝을 포함하는 범위에서는 lo ≤ hi 조건으로 반복하세요.
양 끝을 포함하는 범위에서 lo = mid 또는 hi = mid로 이동하는 경우. lo와 hi가 이웃한 값이면 mid는 lo와 같아지고 범위가 줄어들지 않아 무한 루프가 발생합니다. 이미 nums[mid]를 확인했으므로 mid + 1 또는 mid - 1로 건너뛰세요.
고정 너비 정수에서 (lo + hi) / 2를 계산하는 경우. 인덱스가 약 10^9를 넘으면 합계에서 오버플로가 발생합니다. 여기의 제한은 그보다 훨씬 낮지만, lo + (hi - lo) / 2를 사용하는 것이 안전한 습관입니다.
target을 찾지 못했을 때 lo를 반환하는 경우. 루프가 끝난 뒤 lo는 삽입 위치이며, 유효한 인덱스이지 -1이 아닙니다.
Lua와 R에서의 오프셋을 잊는 경우. 이 언어들의 리스트는 1부터 시작하므로, 반환하는 인덱스는 위치에서 1을 뺀 값입니다.

자주 묻는 질문4

이진 검색의 시간 복잡도는 무엇인가요?

O(log n). 각 비교는 대상이 있을 수 있는 범위를 절반으로 줄이므로, k단계 후에는 최대 n / 2^k개의 후보만 남습니다. 10^4개의 요소가 있는 목록에는 비교가 최대 14회 필요하고, 10^9개의 요소가 있는 목록에는 최대 30회 필요합니다. 반복 버전은 추가 공간을 O(1) 사용합니다.

이진 탐색에는 왜 정렬된 배열이 필요한가요?

목록의 절반을 버리는 단계는 순서에 의존합니다. nums[mid] < target일 때, 정렬되어 있으면 mid의 왼쪽에 있는 모든 요소도 target보다 작다는 것이 보장되므로, 그중 일치하는 요소는 없습니다. 정렬되지 않은 목록에서는 이 비교만으로 다른 요소에 대해 아무것도 알 수 없으므로, 모든 요소를 확인해야 합니다.

이진 탐색은 반복문 방식이어야 할까요, 재귀 방식이어야 할까요?

둘 다 올바르며 O(log n) 시간에 실행됩니다. 재귀 버전은 한쪽 절반을 대상으로 자기 자신을 호출하고 O(log n)의 스택 공간을 사용합니다. 반복 버전은 루프에서 lo와 hi를 이동하며 O(1)을 사용합니다. 면접관은 보통 루프를 기대하며, 루프는 재귀 제한도 피할 수 있습니다.

중간 인덱스를 계산할 때 오버플로를 어떻게 방지하나요?

mid = lo + (hi - lo) / 2를 (lo + hi) / 2 대신 사용하세요. 두 식은 같은 인덱스를 반환하지만, 두 번째 식은 먼저 두 인덱스를 더하므로 32비트 정수에서는 인덱스가 약 1.07 × 10^9를 넘으면 합계가 오버플로됩니다. Python과 Ruby는 정수의 범위가 제한되지 않으므로, 이 언어들에서는 짧은 식도 안전합니다.

Python

def search(nums, target):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

입력

nums = [-7, -2, 0, 4, 9, 15, 23]
target = 9

기대값