C_07_BinarySearch

이진 탐색 (Binary Search)

목차

1. 이진 탐색 개념
2. 시간 복잡도 분석
3. 이진 탐색 구현
4. Python bisect 모듈
5. 이진 탐색 응용
6. 실전 문제 예시
7. 핵심 정리

---

1. 이진 탐색 개념

1.1 정의

이진 탐색(Binary Search) 은 정렬된 데이터에서 탐색 범위를 절반씩 줄여가며 원하는 데이터를 찾는 알고리즘이다.

1.2 전제 조건

중요: 이진 탐색은 데이터가 반드시 정렬되어 있어야 한다!

1.3 핵심 원리

정렬된 배열: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
찾을 값: 7

Step 1: 전체 범위에서 중간값(9) 확인
        [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
                   ↑ (mid)
        7 < 9 이므로 왼쪽 범위로 이동

Step 2: 왼쪽 범위에서 중간값(3) 확인
        [1, 3, 5, 7]
            ↑ (mid)
        7 > 3 이므로 오른쪽 범위로 이동

Step 3: 오른쪽 범위에서 중간값(5) 확인
        [5, 7]
         ↑ (mid)
        7 > 5 이므로 오른쪽으로 이동

Step 4: 찾음!
        [7]
         ↑ 정답!

1.4 순차 탐색 vs 이진 탐색

구분	순차 탐색	이진 탐색
정렬 필요	불필요	필수
시간 복잡도	O(N)	O(log N)
탐색 방식	처음부터 순서대로	중간부터 절반씩
적합한 경우	소량 데이터, 비정렬	대량 데이터, 정렬됨

1.5 이진 탐색의 특징

• 분할 정복(Divide & Conquer) 방식 사용
• 퀵 정렬과 공통점: 범위를 나누어 탐색
• 탐색 범위가 절반씩 감소하여 매우 빠름
• 데이터가 1,000,000개여도 약 20번의 비교로 탐색 가능

---

2. 시간 복잡도 분석

2.1 O(log N)의 의미

N = 데이터 개수
매 단계마다 탐색 범위가 절반으로 감소

N → N/2 → N/4 → N/8 → ... → 1

단계 수 = log₂(N)

2.2 데이터 개수별 비교 횟수

데이터 개수 (N)	순차 탐색 (최악)	이진 탐색 (최악)
10	10회	4회
100	100회	7회
1,000	1,000회	10회
10,000	10,000회	14회
100,000	100,000회	17회
1,000,000	1,000,000회	20회
10억	10억회	30회

2.3 언제 이진 탐색을 사용할까?

"""
이진 탐색 사용 시점 판단

1. 데이터가 정렬되어 있거나 정렬 가능
2. 데이터 크기가 매우 큼 (N > 10,000)
3. 탐색을 여러 번 수행해야 함
4. "~가 존재하는가?" 또는 "~의 최솟값/최댓값"

문제에서 다음 조건이 보이면 이진 탐색 고려:
- 데이터 개수: 10만 ~ 10억
- 시간 제한: 1~2초
- "정렬", "찾기", "탐색", "최적" 키워드
"""

---

3. 이진 탐색 구현

3.1 재귀 함수 방식

def binary_search_recursive(array, target, start, end):
    """
    이진 탐색 (재귀 방식)

    Args:
        array: 정렬된 리스트
        target: 찾고자 하는 값
        start: 탐색 시작 인덱스
        end: 탐색 종료 인덱스

    Returns:
        target의 인덱스 (없으면 None)
    """
    # 기저 조건: 탐색 범위가 없으면 종료
    if start > end:
        return None

    # 중간점 계산
    mid = (start + end) // 2

    # 찾으면 인덱스 반환
    if array[mid] == target:
        return mid

    # 중간값보다 작으면 왼쪽 탐색
    elif array[mid] > target:
        return binary_search_recursive(array, target, start, mid - 1)

    # 중간값보다 크면 오른쪽 탐색
    else:
        return binary_search_recursive(array, target, mid + 1, end)


# 사용 예시
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7

result = binary_search_recursive(array, target, 0, len(array) - 1)
if result is not None:
    print(f"인덱스: {result}")  # 인덱스: 3
else:
    print("데이터가 존재하지 않습니다.")

3.2 반복문 방식 (권장)

def binary_search_iterative(array, target):
    """
    이진 탐색 (반복문 방식)

    Args:
        array: 정렬된 리스트
        target: 찾고자 하는 값

    Returns:
        target의 인덱스 (없으면 None)
    """
    start = 0
    end = len(array) - 1

    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

    return None


# 사용 예시
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
target = 7

result = binary_search_iterative(array, target)
print(f"인덱스: {result}")  # 인덱스: 3

3.3 재귀 vs 반복문

구분	재귀 방식	반복문 방식
코드 가독성	직관적	보통
메모리 사용	많음 (스택 프레임)	적음
성능	함수 호출 오버헤드	빠름
추천 상황	분할 정복 응용	일반적인 탐색

코딩테스트에서는 반복문 방식을 권장

3.4 주의사항

# 1. 중간점 계산 시 오버플로우 방지 (다른 언어에서)
mid = start + (end - start) // 2  # 권장
mid = (start + end) // 2          # Python에서는 문제없음

# 2. 탐색 범위 갱신 시 mid 포함 여부
# target > array[mid] → start = mid + 1 (mid 제외)
# target < array[mid] → end = mid - 1 (mid 제외)

# 3. 종료 조건
# while start <= end (등호 포함!)

---

4. Python bisect 모듈

4.1 bisect 모듈 소개

Python 표준 라이브러리의 bisect 모듈은 이진 탐색을 쉽게 사용할 수 있게 해준다.

from bisect import bisect_left, bisect_right, insort

4.2 주요 함수

함수	설명
bisect_left(a, x)	x가 들어갈 가장 왼쪽 위치 반환
bisect_right(a, x)	x가 들어갈 가장 오른쪽 위치 반환
insort_left(a, x)	x를 왼쪽 위치에 삽입
insort_right(a, x)	x를 오른쪽 위치에 삽입

4.3 bisect_left vs bisect_right

from bisect import bisect_left, bisect_right

array = [1, 2, 4, 4, 4, 6, 8]
x = 4

# bisect_left: x가 들어갈 가장 왼쪽 인덱스
left = bisect_left(array, x)
print(f"bisect_left: {left}")  # 2 (첫 번째 4의 위치)

# bisect_right: x가 들어갈 가장 오른쪽 인덱스
right = bisect_right(array, x)
print(f"bisect_right: {right}")  # 5 (마지막 4 다음 위치)

# x가 몇 개인지 세기
count = right - left
print(f"4의 개수: {count}")  # 3

"""
array = [1, 2, 4, 4, 4, 6, 8]
인덱스:  0  1  2  3  4  5  6

bisect_left(array, 4) = 2  → 인덱스 2에 삽입하면 정렬 유지
bisect_right(array, 4) = 5 → 인덱스 5에 삽입하면 정렬 유지
"""

4.4 값의 존재 여부 확인

from bisect import bisect_left

def binary_search_bisect(array, target):
    """
    bisect를 이용한 이진 탐색
    """
    idx = bisect_left(array, target)

    # 인덱스가 범위 내이고, 해당 위치의 값이 target과 같으면 존재
    if idx < len(array) and array[idx] == target:
        return idx
    return None


# 테스트
array = [1, 3, 5, 7, 9]
print(binary_search_bisect(array, 5))   # 2
print(binary_search_bisect(array, 4))   # None

4.5 특정 범위 내 값의 개수

from bisect import bisect_left, bisect_right

def count_in_range(array, left_value, right_value):
    """
    정렬된 배열에서 [left_value, right_value] 범위 내 원소 개수 반환
    """
    right_idx = bisect_right(array, right_value)
    left_idx = bisect_left(array, left_value)
    return right_idx - left_idx


# 테스트
array = [1, 2, 3, 3, 3, 4, 5, 6, 7, 8]

# 3 이상 5 이하인 원소의 개수
print(count_in_range(array, 3, 5))  # 5 (3, 3, 3, 4, 5)

# 2 이상 4 미만인 원소의 개수
print(count_in_range(array, 2, 3))  # 4 (2, 3, 3, 3)

---

5. 이진 탐색 응용

5.1 Lower Bound / Upper Bound

Lower Bound

특정 값 이상인 첫 번째 원소의 위치

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

    while start < end:
        mid = (start + end) // 2
        if array[mid] >= target:
            end = mid
        else:
            start = mid + 1

    return start


# bisect 사용
from bisect import bisect_left
lower_bound_idx = bisect_left(array, target)

Upper Bound

특정 값 초과인 첫 번째 원소의 위치

def upper_bound(array, target):
    """
    target 초과인 첫 번째 원소의 인덱스 반환
    (없으면 len(array) 반환)
    """
    start, end = 0, len(array)

    while start < end:
        mid = (start + end) // 2
        if array[mid] > target:
            end = mid
        else:
            start = mid + 1

    return start


# bisect 사용
from bisect import bisect_right
upper_bound_idx = bisect_right(array, target)

5.2 파라메트릭 서치 (Parametric Search)

최적화 문제를 결정 문제로 바꾸어 이진 탐색으로 해결하는 기법

최적화 문제: "조건을 만족하는 최댓값/최솟값은?"
     ↓ 변환
결정 문제: "X로 조건을 만족할 수 있는가?" (Yes/No)
     ↓ 이진 탐색
정답 도출

예시: 떡볶이 떡 만들기

"""
문제: 절단기 높이(H)를 설정하면 H 이상인 부분만 잘림
      잘린 떡의 총 길이가 M 이상이 되도록 하는 H의 최댓값은?

입력:
- 떡 개수 N, 요청한 길이 M
- 각 떡의 길이 리스트

예시:
떡: [19, 15, 10, 17]
M = 6
H = 15로 자르면: (19-15) + (15-15) + 0 + (17-15) = 4+0+0+2 = 6
"""

def parametric_search():
    n, m = map(int, input().split())
    rice_cakes = list(map(int, input().split()))

    start = 0
    end = max(rice_cakes)
    result = 0

    while start <= end:
        mid = (start + end) // 2

        # 잘린 떡의 총 길이 계산
        total = sum(max(0, cake - mid) for cake in rice_cakes)

        # 떡의 양이 충분하면 높이를 높임 (더 적게 자르기)
        if total >= m:
            result = mid  # 일단 저장 (최댓값을 찾으므로)
            start = mid + 1
        # 떡의 양이 부족하면 높이를 낮춤 (더 많이 자르기)
        else:
            end = mid - 1

    return result


# 테스트
# 입력: 4 6
#       19 15 10 17
# 출력: 15

5.3 이진 탐색 변형 패턴

# 패턴 1: 정확한 값 찾기
while start <= end:
    mid = (start + end) // 2
    if array[mid] == target:
        return mid
    elif array[mid] < target:
        start = mid + 1
    else:
        end = mid - 1
return -1

# 패턴 2: Lower Bound (target 이상인 최솟값)
while start < end:
    mid = (start + end) // 2
    if array[mid] >= target:
        end = mid
    else:
        start = mid + 1
return start

# 패턴 3: Upper Bound (target 초과인 최솟값)
while start < end:
    mid = (start + end) // 2
    if array[mid] > target:
        end = mid
    else:
        start = mid + 1
return start

# 패턴 4: 조건 만족하는 최댓값
while start <= end:
    mid = (start + end) // 2
    if check(mid):  # 조건 만족
        result = mid
        start = mid + 1  # 더 큰 값 탐색
    else:
        end = mid - 1
return result

# 패턴 5: 조건 만족하는 최솟값
while start <= end:
    mid = (start + end) // 2
    if check(mid):  # 조건 만족
        result = mid
        end = mid - 1  # 더 작은 값 탐색
    else:
        start = mid + 1
return result

---

6. 실전 문제 예시

6.1 부품 찾기

"""
문제: 전자 매장에 N개의 부품이 있음
      손님이 M개의 부품을 요청했을 때 각각 있는지 확인

입력:
N = 5
부품: [8, 3, 7, 9, 2]
M = 3
요청: [5, 7, 9]

출력: No Yes Yes
"""

def binary_search(array, target):
    start, end = 0, len(array) - 1

    while start <= end:
        mid = (start + end) // 2
        if array[mid] == target:
            return True
        elif array[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

    return False


def find_parts():
    n = int(input())
    parts = list(map(int, input().split()))
    m = int(input())
    requests = list(map(int, input().split()))

    # 이진 탐색을 위해 정렬
    parts.sort()

    results = []
    for request in requests:
        if binary_search(parts, request):
            results.append("Yes")
        else:
            results.append("No")

    print(' '.join(results))


# 집합(Set)을 이용한 더 간단한 풀이
def find_parts_using_set():
    n = int(input())
    parts = set(map(int, input().split()))  # O(1) 탐색
    m = int(input())
    requests = list(map(int, input().split()))

    for request in requests:
        print("Yes" if request in parts else "No", end=' ')

6.2 특정 수의 개수 구하기

"""
문제: 정렬된 배열에서 특정 수가 몇 개인지 구하기
      (단, O(logN)으로 해결해야 함)

입력:
N = 7, x = 2
배열: [1, 1, 2, 2, 2, 2, 3]

출력: 4
"""

from bisect import bisect_left, bisect_right

def count_by_value(array, x):
    # x의 개수 = (x보다 큰 첫 인덱스) - (x 이상인 첫 인덱스)
    right_idx = bisect_right(array, x)
    left_idx = bisect_left(array, x)

    count = right_idx - left_idx
    return count if count > 0 else -1


# 테스트
array = [1, 1, 2, 2, 2, 2, 3]
print(count_by_value(array, 2))  # 4
print(count_by_value(array, 4))  # -1 (존재하지 않음)

6.3 나무 자르기 (파라메트릭 서치)

"""
문제: 환경부에서 나무를 일정 높이로 자름
      잘린 나무 합이 최소 M미터가 되도록 하는 절단기 높이의 최댓값

입력:
N = 4, M = 7
나무: [20, 15, 10, 17]

출력: 15
"""

def cut_trees():
    n, m = map(int, input().split())
    trees = list(map(int, input().split()))

    start = 0
    end = max(trees)
    result = 0

    while start <= end:
        mid = (start + end) // 2

        # 잘린 나무의 합 계산
        total = 0
        for tree in trees:
            if tree > mid:
                total += (tree - mid)

        # 충분히 얻었으면 높이를 높임
        if total >= m:
            result = mid
            start = mid + 1
        else:
            end = mid - 1

    return result


# 더 간결한 방식
def cut_trees_pythonic():
    n, m = map(int, input().split())
    trees = list(map(int, input().split()))

    start, end = 0, max(trees)
    result = 0

    while start <= end:
        mid = (start + end) // 2
        total = sum(max(0, tree - mid) for tree in trees)

        if total >= m:
            result = mid
            start = mid + 1
        else:
            end = mid - 1

    return result

6.4 랜선 자르기

"""
문제: K개의 랜선을 잘라 N개의 같은 길이 랜선을 만들 때
      랜선의 최대 길이

입력:
K = 4, N = 11
랜선: [802, 743, 457, 539]

출력: 200
"""

def cut_lan_cables():
    k, n = map(int, input().split())
    cables = [int(input()) for _ in range(k)]

    start = 1
    end = max(cables)
    result = 0

    while start <= end:
        mid = (start + end) // 2

        # mid 길이로 자르면 몇 개가 나오는지
        count = sum(cable // mid for cable in cables)

        if count >= n:  # N개 이상 만들 수 있으면
            result = mid
            start = mid + 1
        else:
            end = mid - 1

    return result

---

7. 핵심 정리

7.1 이진 탐색 핵심

1. 전제조건: 데이터가 정렬되어 있어야 함
2. 시간복잡도: O(log N) - 매우 빠름
3. 구현방식: 재귀 또는 반복문 (반복문 권장)
4. 핵심로직: 중간값과 비교하여 탐색 범위를 절반으로 줄임

7.2 코딩테스트 팁

상황	접근법
정확한 값 찾기	기본 이진 탐색
값의 개수 세기	bisect_left, bisect_right
최댓값/최솟값 구하기	파라메트릭 서치
범위 내 원소 찾기	Lower/Upper Bound

7.3 자주 하는 실수

실수	해결 방법
정렬 안 함	탐색 전 반드시 정렬
종료 조건 틀림	start <= end (등호 포함)
범위 갱신 틀림	mid - 1, mid + 1 (mid 제외)
무한 루프	범위가 줄어드는지 확인

7.4 bisect 모듈 정리

from bisect import bisect_left, bisect_right

array = [1, 2, 4, 4, 4, 6, 8]
x = 4

# x가 들어갈 가장 왼쪽 위치 (x 이상인 첫 위치)
bisect_left(array, x)   # 2

# x가 들어갈 가장 오른쪽 위치 (x 초과인 첫 위치)
bisect_right(array, x)  # 5

# x의 개수
bisect_right(array, x) - bisect_left(array, x)  # 3

7.5 문제 유형 판별

"정렬된 데이터에서 ~를 찾아라" → 기본 이진 탐색
"~의 개수를 구하라" → bisect 사용
"조건을 만족하는 최대/최소" → 파라메트릭 서치
"N이 10억 이상" → 이진 탐색 필수

---

참고 자료

• 이진 탐색은 데이터가 정렬되어 있을 때만 사용 가능
• 파라메트릭 서치는 최적화 문제를 결정 문제로 변환
• Python의 bisect 모듈을 활용하면 구현이 간단해짐
• 데이터가 매우 클 때 (10만 이상) 이진 탐색 고려