이분 탐색(Binary Search) 완벽 가이드 – 알고리즘 원리부터 코딩테스트 응용까지

이분 탐색이란?

이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾는 가장 효율적인 탐색 알고리즘입니다. 배열을 반으로 나누어 탐색 범위를 절반씩 줄여나가는 분할 정복(Divide and Conquer) 기법을 사용합니다.

핵심 포인트: 이분 탐색은 반드시 정렬된 자료구조에서만 사용할 수 있습니다.

선형 탐색 vs 이분 탐색

비교 항목	선형 탐색	이분 탐색
시간 복잡도	$O(n)$ $O (n)$	$O(\log n)$ $O (lo g n)$
정렬 필요 여부	불필요	필수
구현 난이도	쉬움	보통
사용 사례	작은 배열, 정렬 안 됨	큰 배열, 정렬됨

예시: 1,000,000개의 원소에서 값을 찾을 때
– 선형 탐색: 최악 1,000,000번 비교
– 이분 탐색: 최악 20번 비교 ( $\log_2 1000000 \approx 20$ $lo g_{2} 1000000 \approx 20$ )

이분 탐색의 핵심 원리

동작 과정

중간 인덱스 계산: mid = (left + right) // 2
비교 및 범위 조정:
– arr[mid] == target: 찾음! 인덱스 반환
– arr[mid] < target: 오른쪽 절반 탐색 (left = mid + 1)
– arr[mid] > target: 왼쪽 절반 탐색 (right = mid - 1)
반복: left > right가 될 때까지 반복

시각화 예제

배열 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]에서 7을 찾는 과정:

초기 상태: left=0, right=9
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
           ↑           ↑
         left         right
         mid=4 → arr[4]=9 > 7

1단계: right=3
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
 ↑     ↑
left  right
mid=1 → arr[1]=3 < 7

2단계: left=2
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
     ↑  ↑
   left right
   mid=2 → arr[2]=5 < 7

3단계: left=3
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
        ↑
    left=right=3
    mid=3 → arr[3]=7 ✓ 찾음!

기본 구현 (반복문)

def binary_search(arr, target):
    """
    정렬된 배열에서 target 값의 인덱스를 반환

    시간 복잡도: O(log n)
    공간 복잡도: O(1)
    """
    left, right = 0, len(arr) - 1

    while left <= right:
        # 오버플로우 방지: (left + right) // 2 대신 이 방식 권장
        mid = left + (right - left) // 2

        if arr[mid] == target:
            return mid  # 찾은 경우 인덱스 반환
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽 절반 탐색
        else:
            right = mid - 1  # 왼쪽 절반 탐색

    return -1  # 못 찾은 경우

# 테스트
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(arr, 7))   # 출력: 3
print(binary_search(arr, 10))  # 출력: -1 (없음)

중간 인덱스 계산 주의사항

# ❌ 오버플로우 위험 (큰 배열에서 left + right가 int 범위 초과 가능)
mid = (left + right) // 2

# ✅ 안전한 방법
mid = left + (right - left) // 2

재귀 구현

def binary_search_recursive(arr, target, left, right):
    """
    재귀 방식의 이분 탐색

    시간 복잡도: O(log n)
    공간 복잡도: O(log n) - 재귀 호출 스택
    """
    if left > right:
        return -1  # 기저 사례: 못 찾음

    mid = left + (right - left) // 2

    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# 테스트
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search_recursive(arr, 13, 0, len(arr) - 1))  # 출력: 6

반복 vs 재귀

구분	반복문	재귀
공간 복잡도	$O(1)$ $O (1)$	$O(\log n)$ $O (lo g n)$
성능	더 빠름 (함수 호출 오버헤드 없음)	약간 느림
가독성	보통	높음 (논리가 직관적)
스택 오버플로우	없음	매우 큰 배열에서 가능

코딩테스트 권장: 반복문 방식 (공간 복잡도 최적화)

복잡도 분석

시간 복잡도: $O(\log n)$ $O (lo g n)$

매 단계마다 탐색 범위가 절반으로 줄어듭니다.

1단계: $n$ $n$ 개
2단계: $\frac{n}{2}$ 개
3단계: $\frac{n}{4}$ 개
…
$k$ $k$ 단계: $\frac{n}{2^k} = 1$

$2^k = n \Rightarrow k = \log_2 n$ $2^{k} = n \Rightarrow k = lo g_{2} n$

따라서 최대 $\log_2 n$ $lo g_{2} n$ 번의 비교가 필요합니다.

공간 복잡도

반복문: $O(1)$ $O (1)$ – 고정된 변수만 사용
재귀: $O(\log n)$ $O (lo g n)$ – 재귀 호출 스택 깊이

이분 탐색 변형 문제

1. Lower Bound (하한선)

정의: target 이상인 첫 번째 원소의 인덱스

def lower_bound(arr, target):
    """
    target 이상인 첫 번째 원소의 인덱스 반환
    없으면 len(arr) 반환

    예: [1, 2, 4, 4, 6], target=4 → 2
    """
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] < target:
            left = mid + 1  # target 이상을 찾아야 하므로 오른쪽으로
        else:
            right = mid  # arr[mid] >= target, 더 왼쪽에 있을 수 있음

    return left

# 테스트
arr = [1, 2, 4, 4, 6, 8]
print(lower_bound(arr, 4))   # 출력: 2
print(lower_bound(arr, 5))   # 출력: 4 (6의 인덱스)
print(lower_bound(arr, 10))  # 출력: 6 (배열 끝)

2. Upper Bound (상한선)

정의: target 초과인 첫 번째 원소의 인덱스

def upper_bound(arr, target):
    """
    target 초과인 첫 번째 원소의 인덱스 반환

    예: [1, 2, 4, 4, 6], target=4 → 4
    """
    left, right = 0, len(arr)

    while left < right:
        mid = left + (right - left) // 2

        if arr[mid] <= target:
            left = mid + 1  # target 초과를 찾아야 하므로
        else:
            right = mid

    return left

# 테스트
arr = [1, 2, 4, 4, 6, 8]
print(upper_bound(arr, 4))   # 출력: 4 (6의 인덱스)
print(upper_bound(arr, 5))   # 출력: 4

3. 중복 원소 개수 세기

def count_occurrences(arr, target):
    """
    정렬된 배열에서 target의 등장 횟수

    시간 복잡도: O(log n)
    """
    left = lower_bound(arr, target)
    right = upper_bound(arr, target)

    return right - left

# 테스트
arr = [1, 2, 4, 4, 4, 6, 8]
print(count_occurrences(arr, 4))  # 출력: 3
print(count_occurrences(arr, 5))  # 출력: 0

파라메트릭 서치 (Parametric Search)

이분 탐색을 결정 문제(예/아니오)로 확장한 응용 기법입니다.

핵심: “조건을 만족하는 최솟값/최댓값은?” 형태의 문제

전형적인 문제 패턴

“최소 시간은?”
“최대 용량은?”
“최소 거리는?”

예제: 나무 자르기 (백준 2805)

문제: 높이 H로 나무를 자를 때, 필요한 나무 M미터 이상을 얻을 수 있는 최대 H는?

def can_cut(trees, height, target):
    """
    height로 자를 때 target 이상 얻을 수 있는지 판단

    시간 복잡도: O(n)
    """
    total = sum(max(0, tree - height) for tree in trees)
    return total >= target

def solve_tree_cutting(trees, target):
    """
    파라메트릭 서치로 최대 절단 높이 찾기

    시간 복잡도: O(n log max_height)
    """
    left, right = 0, max(trees)  # 높이 범위
    result = 0

    while left <= right:
        mid = left + (right - left) // 2

        if can_cut(trees, mid, target):
            result = mid  # 가능하면 기록하고 더 높은 값 시도
            left = mid + 1
        else:
            right = mid - 1  # 불가능하면 높이 낮춤

    return result

# 테스트
trees = [20, 15, 10, 17]
target = 7
print(solve_tree_cutting(trees, target))  # 출력: 15
# 설명: 15로 자르면 5+0+0+2=7 (정확히 만족)

단계별 동작 과정

trees = [20, 15, 10, 17], target = 7

1단계: left=0, right=20, mid=10
  → 자른 양: 10+5+0+7=22 ≥ 7 ✓
  → result=10, left=11

2단계: left=11, right=20, mid=15
  → 자른 양: 5+0+0+2=7 ≥ 7 ✓
  → result=15, left=16

3단계: left=16, right=20, mid=18
  → 자른 양: 2+0+0+0=2 < 7 ✗
  → right=17

4단계: left=16, right=17, mid=16
  → 자른 양: 4+0+0+1=5 < 7 ✗
  → right=15

5단계: left=16 > right=15 종료
최종 답: 15

자주 하는 실수와 엣지 케이스

1. 종료 조건 실수

# ❌ 무한 루프 위험
while left < right:  # left == right일 때 탐색 누락
    ...

# ✅ 올바른 조건
while left <= right:
    ...

2. 범위 업데이트 실수

# ❌ 무한 루프 가능
if arr[mid] < target:
    left = mid  # mid가 그대로 유지될 수 있음

# ✅ 올바른 업데이트
if arr[mid] < target:
    left = mid + 1

3. 빈 배열 처리

def binary_search_safe(arr, target):
    if not arr:  # 빈 배열 체크
        return -1

    left, right = 0, len(arr) - 1
    # ... 나머지 로직

4. 정렬되지 않은 배열

# 이분 탐색 전 반드시 정렬 확인
arr = [3, 1, 4, 1, 5, 9, 2, 6]
arr.sort()  # 정렬 필수!
result = binary_search(arr, 5)

5. 오버플로우 (큰 인덱스)

# ❌ Java/C++에서 int 오버플로우 가능
mid = (left + right) / 2

# ✅ 안전한 방법
mid = left + (right - left) // 2

난이도별 접근 전략

쉬움: 기본 이분 탐색

특징: 정렬된 배열, 중복 없음, 단순 존재 여부
예제: 특정 값 찾기
시간: $O(\log n)$ $O (lo g n)$

# 템플릿
while left <= right:
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

보통: Lower/Upper Bound

특징: 중복 원소, 범위 찾기
예제: 특정 값의 개수, 범위 질의
주의: left < right 조건, right = len(arr) 초기화

# Lower Bound 템플릿
while left < right:
    mid = left + (right - left) // 2
    if arr[mid] < target:
        left = mid + 1
    else:
        right = mid  # mid를 포함해야 함

어려움: 파라메트릭 서치

특징: 최적화 문제를 결정 문제로 변환
예제: 나무 자르기, 공유기 설치, 랜선 자르기
핵심: can_solve(mid) 함수 정의

# 템플릿
def can_solve(value):
    # 해당 값으로 문제를 해결할 수 있는지 판단
    pass

result = -1
while left <= right:
    mid = left + (right - left) // 2
    if can_solve(mid):
        result = mid  # 가능하면 기록
        # 최댓값 찾기: left = mid + 1
        # 최솟값 찾기: right = mid - 1
    else:
        # 범위 조정
        pass

Python 내장 함수: bisect 모듈

Python은 이분 탐색을 위한 내장 모듈을 제공합니다.

import bisect

arr = [1, 3, 5, 7, 9, 11]

# 1. bisect_left: Lower Bound
index = bisect.bisect_left(arr, 5)
print(index)  # 출력: 2

# 2. bisect_right (bisect): Upper Bound
index = bisect.bisect_right(arr, 5)
print(index)  # 출력: 3

# 3. 값 삽입 (정렬 유지)
bisect.insort(arr, 6)
print(arr)  # 출력: [1, 3, 5, 6, 7, 9, 11]

# 4. 중복 원소 개수
def count_range(arr, target):
    left = bisect.bisect_left(arr, target)
    right = bisect.bisect_right(arr, target)
    return right - left

arr = [1, 2, 4, 4, 4, 6, 8]
print(count_range(arr, 4))  # 출력: 3

bisect 함수 비교

함수	설명	용도
`bisect_left(arr, x)`	x 이상인 첫 인덱스	Lower Bound
`bisect_right(arr, x)`	x 초과인 첫 인덱스	Upper Bound
`insort_left(arr, x)`	x를 왼쪽에 삽입	정렬 유지 삽입
`insort_right(arr, x)`	x를 오른쪽에 삽입	정렬 유지 삽입

실전 문제 풀이

문제 1: 숫자 카드 2 (백준 10816)

문제: N개의 카드 중 각 숫자의 개수를 구하라.

import bisect

def solve_number_cards():
    n = int(input())
    cards = sorted(map(int, input().split()))

    m = int(input())
    queries = list(map(int, input().split()))

    results = []
    for q in queries:
        # Lower와 Upper Bound 차이가 개수
        left = bisect.bisect_left(cards, q)
        right = bisect.bisect_right(cards, q)
        results.append(right - left)

    print(' '.join(map(str, results)))

# 예제 입력:
# 10
# 6 3 2 10 10 10 -10 -10 7 3
# 8
# 10 9 -5 2 3 4 5 -10
# 출력: 3 0 0 1 2 0 0 2

시간 복잡도: $O(n \log n + m \log n)$ $O (n lo g n + m lo g n)$
– 정렬: $O(n \log n)$ $O (n lo g n)$
– 각 쿼리: $O(\log n)$ $O (lo g n)$ , $m$ $m$ 개 → $O(m \log n)$ $O (m lo g n)$

문제 2: 공유기 설치 (백준 2110)

문제: N개의 집에 C개의 공유기를 설치하되, 가장 인접한 두 공유기 사이의 거리를 최대화하라.

def can_install(houses, count, min_dist):
    """
    최소 거리 min_dist를 유지하며 count개 설치 가능한지 판단

    시간 복잡도: O(n)
    """
    installed = 1  # 첫 집에 설치
    last_pos = houses[0]

    for i in range(1, len(houses)):
        if houses[i] - last_pos >= min_dist:
            installed += 1
            last_pos = houses[i]

            if installed >= count:
                return True

    return False

def solve_router():
    n, c = map(int, input().split())
    houses = sorted([int(input()) for _ in range(n)])

    # 거리 범위: 1 ~ (최대 좌표 - 최소 좌표)
    left, right = 1, houses[-1] - houses[0]
    result = 0

    while left <= right:
        mid = left + (right - left) // 2

        if can_install(houses, c, mid):
            result = mid  # 가능하면 기록하고 더 큰 거리 시도
            left = mid + 1
        else:
            right = mid - 1

    print(result)

# 예제 입력:
# 5 3
# 1
# 2
# 8
# 4
# 9
# 출력: 3 (1, 4, 8 또는 1, 4, 9에 설치)

시간 복잡도: $O(n \log n + n \log D)$ $O (n lo g n + n lo g D)$
– 정렬: $O(n \log n)$ $O (n lo g n)$
– 이분 탐색: $O(\log D)$ $O (lo g D)$ × 검증 $O(n)$ $O (n)$ → $O(n \log D)$ $O (n lo g D)$
– $D$ $D$ 는 좌표 범위 (최대 $10^9$ $1 0^{9}$ )

이분 탐색 체크리스트

문제 적용 가능 여부

[ ] 자료가 정렬되어 있는가? (또는 정렬 가능한가?)
[ ] “최대” 또는 “최소”를 구하는 문제인가?
[ ] 조건을 만족하는지 $O(n)$ $O (n)$ 이하로 판단 가능한가?
[ ] 답의 범위가 명확한가?

구현 체크리스트

[ ] 초기 left, right 범위가 올바른가?
[ ] 중간 인덱스 계산이 오버플로우 안전한가?
[ ] 종료 조건이 left <= right인가?
[ ] 범위 업데이트 시 mid ± 1을 사용하는가?
[ ] 엣지 케이스 처리 (빈 배열, 단일 원소)?
[ ] Lower/Upper Bound에서 right = len(arr)로 초기화했는가?

마무리

이분 탐색은 정렬된 데이터에서 $O(\log n)$ $O (lo g n)$ 시간 복잡도를 보장하는 강력한 알고리즘입니다. 핵심 개념을 정리하면:

핵심 요약

기본 원리: 중간 값과 비교 → 절반씩 범위 축소
시간 복잡도: $O(\log n)$ $O (lo g n)$ (선형 탐색 $O(n)$ $O (n)$ 보다 압도적으로 빠름)
전제 조건: 반드시 정렬된 배열
변형 기법:
– Lower Bound: target 이상인 첫 인덱스
– Upper Bound: target 초과인 첫 인덱스
– Parametric Search: 최적화 문제를 결정 문제로 변환
실수 방지:
– 오버플로우: left + (right - left) // 2
– 종료 조건: while left <= right
– 범위 업데이트: mid ± 1

학습 로드맵

단계	주제	추천 문제
1	기본 이분 탐색	백준 1920 (수 찾기)
2	Lower/Upper Bound	백준 10816 (숫자 카드 2)
3	파라메트릭 서치	백준 2805 (나무 자르기)
4	응용	백준 2110 (공유기 설치)
5	고급	백준 1300 (K번째 수)

실전 팁: Python에서는 bisect 모듈을 적극 활용하되, 면접에서는 직접 구현할 수 있어야 합니다.

이분 탐색은 코딩테스트 필수 알고리즘이며, 특히 시간 복잡도 최적화가 필요한 문제에서 빈번하게 출제됩니다. 기본 구현부터 파라메트릭 서치까지 단계별로 연습하여 완벽하게 마스터하시기 바랍니다!

이 글이 도움이 되셨나요?

Buy me a coffee