DSA Interview Prep · 강의

고전적인 이진 검색: 왼쪽, 오른쪽, 중간

Q: “고전적인 이진 검색: 왼쪽, 오른쪽, 중간” 강의는 무료인가요?

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

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

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

Q: “고전적인 이진 검색: 왼쪽, 오른쪽, 중간” 강의는 얼마나 걸리나요?

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

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

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

이진 검색을 반복문과 재귀로 구현하고 lo/hi 경계의 경계 초과 세부 사항을 익힌 뒤, 경계 사례 입력으로 정확성을 검증합니다.

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

이진 탐색이 중요한 이유

이진 탐색은 매 단계마다 탐색 범위를 절반으로 줄여 O(n) 선형 순회를 O(log n)으로 낮춥니다. 원소가 100만 개인 배열에서는 선형 순회에 최대 1,000,000번의 비교가 필요하지만, 이진 탐색에는 최대 20번이면 충분합니다. 이러한 효율성 때문에 이진 탐색은 코딩 면접에서 가장 자주 출제되는 알고리즘 중 하나입니다.

핵심 통찰은 정렬된 배열에서는 한 번만 비교해도 남은 데이터 중 어느 절반을 완전히 버릴지 결정할 수 있다는 점입니다.

왼쪽, 중간, 오른쪽 프레임워크

이진 탐색은 세 개의 인덱스 포인터를 사용합니다. lo는 왼쪽 경계, hi는 오른쪽 경계, mid는 중간점입니다. 각 반복에서 mid = (lo + hi) // 2를 계산하고 대상 값을 arr[mid]와 비교합니다. 대상 값이 더 작으면 hi = mid - 1로 이동하고, 더 크면 lo = mid + 1로 이동하며, 같으면 찾은 것입니다.

반복문은 lo <= hi인 동안 계속됩니다. 대상을 찾지 못한 채 반복문이 종료되면 -1을 반환합니다.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9, 11], 7))  # 3
print(binary_search([1, 3, 5, 7, 9, 11], 6))  # -1

중간점에서 정수 오버플로 피하기

mid = (lo + hi) // 2라는 표현식은 고정 폭 정수를 사용하는 언어(Java, C++)에서 정수 오버플로를 일으킬 수 있습니다. 파이썬의 정수는 임의 정밀도를 사용하므로 오버플로가 발생하지 않지만, 면접에서는 안전한 대안인 mid = lo + (hi - lo) // 2도 알고 있어야 합니다.

이 방식은 같은 중간점을 계산하면서 두 포인터를 먼저 더하는 대신 거리의 절반만 lo에 더합니다. 면접에서 이를 언급하면 저수준의 고려 사항까지 이해하고 있음을 보여 줄 수 있습니다.

# Safe mid calculation (important in Java/C++, good habit in Python too)
lo, hi = 0, 1_000_000_000
mid_unsafe = (lo + hi) // 2   # fine in Python
mid_safe   = lo + (hi - lo) // 2  # same result, no overflow risk
print(mid_unsafe == mid_safe)  # True

포함 경계와 제외 경계

이진 탐색에서 가장 까다로운 부분 중 하나는 hi가 마지막 유효 인덱스를 가리키도록 할지(포함 방식, hi = len(arr) - 1), 아니면 끝의 바로 다음 위치를 가리키도록 할지(제외 방식, hi = len(arr))를 선택하는 것입니다. 관례에 따라 반복 조건과 경계 갱신 방식이 달라집니다.

포함 경계에서는 while lo <= hi를 사용하고 hi = mid - 1로 갱신합니다. 제외 경계에서는 while lo < hi를 사용하고 hi = mid로 갱신합니다. 두 관례를 섞는 것이 이진 탐색 구현에서 오류가 발생하는 가장 흔한 원인입니다.

# Exclusive hi variant — useful for bisect-style lower-bound
def search_exclusive(arr, target):
    lo, hi = 0, len(arr)  # hi is one past last
    while lo < hi:          # strictly less than
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid         # NOT mid - 1
    return lo if lo < len(arr) and arr[lo] == target else -1

print(search_exclusive([2, 4, 6, 8, 10], 6))  # 2

재귀적 이진 탐색

이진 탐색은 갱신된 lo와 hi 경계를 호출 스택을 통해 전달하는 방식으로 재귀적으로 작성할 수 있습니다. 각 재귀 호출은 탐색 범위를 절반으로 줄이므로 깊이는 O(log n)입니다. 기본 사례는 lo > hi인 경우(찾지 못함) 또는 arr[mid] == target인 경우(찾음)입니다.

반복형 버전은 스택 프레임 오버헤드를 피할 수 있으므로 운영 코드에서 선호됩니다. 하지만 화이트보드에서는 재귀형 버전이 분할 정복 구조를 더 명확하게 보여 줍니다.

def binary_search_rec(arr, target, lo, hi):
    if lo > hi:
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_rec(arr, target, mid + 1, hi)
    else:
        return binary_search_rec(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search_rec(arr, 9, 0, len(arr) - 1))  # 4

경계 사례: 빈 배열과 단일 원소

견고한 이진 탐색은 오류 없이 경계 사례를 처리해야 합니다. 가장 흔한 세 가지 경우는 다음과 같습니다. 빈 배열(반복문이 실행되지 않고 -1이 올바르게 반환됨), 단일 원소 배열(mid, lo, hi가 모두 같으므로 한 번의 비교로 충분함), 범위 밖의 대상 값(결국 lo가 hi를 초과하고 -1이 반환됨)입니다.

면접에서 추가 질문으로 넘어가기 전에 항상 이러한 입력으로 구현을 검증하십시오.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([], 5))       # -1  (empty)
print(binary_search([7], 7))      # 0   (single, found)
print(binary_search([7], 3))      # -1  (single, not found)
print(binary_search([1,3,5], 0))  # -1  (below range)
print(binary_search([1,3,5], 9))  # -1  (above range)

시간 및 공간 복잡도

이진 탐색은 각 비교에서 탐색 범위를 절반으로 줄이므로 O(log n) 시간 복잡도를 가집니다. k번 비교한 후 남은 범위는 n/2^k이고, 이 값이 1이 되면 탐색이 끝나므로 k = log₂ n입니다.

공간 복잡도는 반복형 버전에서 O(1)입니다(정수 변수 세 개만 사용). 재귀형 버전에서는 호출 스택의 깊이 때문에 O(log n)입니다. 면접에서는 항상 두 복잡도를 모두 말하고, 공간이 제한된 경우에는 반복형을 선호하십시오.

import math

for n in [10, 100, 1000, 1_000_000, 1_000_000_000]:
    steps = math.ceil(math.log2(n + 1))
    print(f'n={n:>12,}  max comparisons={steps}')

정확한 일치와 경계 찾기

고전적인 이진 탐색은 대상 값이 존재하는 아무 인덱스나 반환합니다. 하지만 많은 면접 문제에서는 대상 값의 첫 번째 또는 마지막 등장 위치를 요구합니다. 이런 경우에는 일치하는 값을 찾은 뒤에도 계속 탐색해야 합니다. 즉시 반환하는 대신 경계를 좁히면서 탐색을 이어 가야 합니다.

첫 번째 등장 위치를 찾을 때 arr[mid] == target을 발견하면 mid를 후보로 기록하고 hi = mid - 1로 설정합니다. 마지막 등장 위치를 찾을 때는 lo = mid + 1로 설정합니다.

def first_occurrence(arr, target):
    lo, hi, result = 0, len(arr) - 1, -1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            result = mid
            hi = mid - 1   # keep searching left
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return result

print(first_occurrence([1, 2, 2, 2, 3], 2))  # 1

파이썬의 bisect 모듈 사용

파이썬 표준 라이브러리는 실전에서 바로 사용할 수 있는 이진 탐색을 위해 bisect.bisect_left(arr, x)와 bisect.bisect_right(arr, x)를 제공합니다. bisect_left는 배열의 정렬 상태를 유지하면서 x를 삽입할 수 있는 가장 왼쪽 인덱스를 반환하며, 사실상 arr[i] >= x를 만족하는 첫 번째 위치를 찾습니다.

면접관이 bisect 사용을 허용할 수도 있지만, 항상 먼저 확인하십시오. bisect가 내부적으로 어떻게 작동하는지(즉 O(log n) 이진 탐색이라는 점)를 아는 것도 여전히 필수입니다.

import bisect

arr = [1, 2, 2, 2, 3, 5]

print(bisect.bisect_left(arr, 2))   # 1  (first 2)
print(bisect.bisect_right(arr, 2))  # 4  (after last 2)

# Check if target exists
target = 3
idx = bisect.bisect_left(arr, target)
print(idx < len(arr) and arr[idx] == target)  # True

이진 탐색에서 흔히 발생하는 오류

면접에서 이진 탐색 오류의 대부분을 일으키는 실수는 세 가지입니다. 첫째, 잘못된 반복 조건입니다. 포함 경계에서 <를 <= 대신 사용하면 마지막으로 남은 원소를 건너뛰게 됩니다. 둘째, 잘못된 경계 갱신입니다. +1 또는 -1을 빠뜨리면 lo == hi일 때 무한 반복이 발생합니다. 셋째, 정렬되지 않은 배열에서 수행하는 것입니다. 이진 탐색은 정렬된 데이터에서만 올바르게 작동합니다.

이진 탐색을 작성하기 전에 항상 다음과 같이 소리 내어 말하십시오. ‘배열은 정렬되어 있고, 경계는 포함 방식이며, lo <= hi인 동안 반복문이 실행됩니다.’

# BUG: infinite loop when lo == hi because hi = mid never moves past lo
def buggy(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:              # should be lo <= hi for exact-match
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid            # stops, but never returns mid when found
    return lo if arr[lo] == target else -1

print(buggy([1, 3, 5, 7], 7))  # 3 (works here by luck)
print(buggy([1, 3, 5, 7], 1))  # 0 (correct)
print(buggy([1, 3, 5, 7], 4))  # -1 (correct)

이진 탐색 면접 팁

정렬된 배열, 단조 증가 함수 또는 절반으로 줄일 수 있는 탐색 범위가 보이면 즉시 이진 탐색을 고려하십시오. 면접에서는 다음과 같이 사고 과정을 설명하십시오. ‘배열이 정렬되어 있으므로 비교 한 번마다 원소의 절반을 버릴 수 있고, 따라서 O(log n)입니다.’

항상 최소 세 가지 입력으로 해답을 검증하십시오. 시작 부분의 값, 끝부분의 값, 그리고 존재하지 않는 값입니다. 질문을 받기 전에 ‘시간 O(log n), 공간 O(1)’처럼 복잡도를 먼저 말하면 기본기가 탄탄하다는 인상을 줄 수 있습니다.

빠른 확인

이번 수업에서 다룬 자료 구조 및 알고리즘 — 코딩 인터뷰 준비 개념에 대한 이해도를 확인해 보십시오.

수업 복습

이번 수업에서 배운 내용은 다음과 같습니다. 이진 탐색은 매 단계마다 탐색 범위를 절반으로 줄여 O(log n) 시간에 동작합니다. 또한 포함 경계 관례에서는 lo <= hi를 사용하고 lo = mid+1 및 hi = mid-1로 갱신합니다. 그리고 첫 번째 또는 마지막 등장 위치를 찾으려면 일치한 즉시 반환하지 말고 탐색을 계속해야 합니다. 다음으로 이진 탐색을 회전된 배열과 정렬되지 않은 배열에 어떻게 확장하는지 살펴보겠습니다.

자주 묻는 질문