이진 탐색 (Binary Search)

개념

정렬된 배열에서 중간값과 비교하여 탐색 범위를 절반씩 줄여가는 알고리즘

“반으로 나누어 탐색” - Divide and Conquer

---

시간복잡도

케이스	시간복잡도
최선	O(1)
평균	O(log n)
최악	O(log n)
공간복잡도	O(1) (반복), O(log n) (재귀)

---

특징

장점

• 매우 빠름: O(log n) 시간복잡도
• 효율적: 큰 데이터에서도 빠른 탐색
• 간단한 구현: 반복문 또는 재귀로 구현

단점

• 정렬 필요: 반드시 정렬된 배열이어야 함
• 정적 데이터: 삽입/삭제가 빈번하면 비효율

---

구현 방법

반복문 구현 (추천)

def binary_search(arr, target):
    """이진 탐색 - 반복문"""
    left = 0
    right = len(arr) - 1
 
    while left <= right:
        mid = (left + right) // 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]
print(binary_search(arr, 7))   # 3
print(binary_search(arr, 10))  # -1
 
# 시간복잡도: O(log n)
# 공간복잡도: O(1)

---

재귀 구현

def binary_search_recursive(arr, target, left, right):
    """이진 탐색 - 재귀"""
    # 기저 조건
    if left > right:
        return -1
 
    mid = (left + right) // 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]
print(binary_search_recursive(arr, 7, 0, len(arr) - 1))  # 3
 
# 시간복잡도: O(log n)
# 공간복잡도: O(log n) - 재귀 스택

---

Python bisect 모듈

import bisect
 
arr = [1, 3, 5, 7, 9, 11, 13, 15]
 
# bisect_left: target 이상인 첫 위치
index = bisect.bisect_left(arr, 7)
print(index)  # 3
 
# bisect_right: target 초과인 첫 위치
index = bisect.bisect_right(arr, 7)
print(index)  # 4
 
# 존재 여부 확인
def binary_search_bisect(arr, target):
    i = bisect.bisect_left(arr, target)
    if i < len(arr) and arr[i] == target:
        return i
    return -1
 
print(binary_search_bisect(arr, 7))   # 3
print(binary_search_bisect(arr, 10))  # -1

---

동작 과정

배열: [1, 3, 5, 7, 9, 11, 13, 15]
찾는 값: 7

1회차:
left=0, right=7, mid=3
arr[3] = 7 = target  ✓ 발견!

결과: 인덱스 3 반환

배열: [1, 3, 5, 7, 9, 11, 13, 15]
찾는 값: 11

1회차:
left=0, right=7, mid=3
arr[3] = 7 < 11  → left = 4

2회차:
left=4, right=7, mid=5
arr[5] = 11 = target  ✓ 발견!

결과: 인덱스 5 반환

---

템플릿

def binary_search_template(arr, target):
    left = 0
    right = len(arr) - 1
 
    while left <= right:
        # 중간 인덱스 계산
        mid = (left + right) // 2
 
        # 비교
        if arr[mid] == target:
            return mid  # 찾음
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽 절반 탐색
        else:
            right = mid - 1  # 왼쪽 절반 탐색
 
    return -1  # 찾지 못함

---

변형 문제 패턴

1. Lower Bound (이상)

def lower_bound(arr, target):
    """target 이상인 첫 번째 위치"""
    left = 0
    right = len(arr)
 
    while left < right:
        mid = (left + right) // 2
 
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
 
    return left
 
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(lower_bound(arr, 2))  # 1 (첫 번째 2)
print(lower_bound(arr, 6))  # 7 (6보다 큰 값 없음)
 
# bisect.bisect_left와 동일

---

2. Upper Bound (초과)

def upper_bound(arr, target):
    """target을 초과하는 첫 번째 위치"""
    left = 0
    right = len(arr)
 
    while left < right:
        mid = (left + right) // 2
 
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
 
    return left
 
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(upper_bound(arr, 2))  # 4 (2보다 큰 첫 값 3)
print(upper_bound(arr, 5))  # 7
 
# bisect.bisect_right와 동일

---

3. 첫 번째/마지막 위치 찾기

def find_first(arr, target):
    """target이 처음 나타나는 위치"""
    left = 0
    right = len(arr) - 1
    result = -1
 
    while left <= right:
        mid = (left + right) // 2
 
        if arr[mid] == target:
            result = mid
            right = mid - 1  # 더 왼쪽 탐색
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return result
 
def find_last(arr, target):
    """target이 마지막으로 나타나는 위치"""
    left = 0
    right = len(arr) - 1
    result = -1
 
    while left <= right:
        mid = (left + right) // 2
 
        if arr[mid] == target:
            result = mid
            left = mid + 1  # 더 오른쪽 탐색
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return result
 
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(find_first(arr, 2))  # 1
print(find_last(arr, 2))   # 3

---

핵심 요약

개념	설명
원리	중간값 비교로 범위를 절반씩 줄임
시간복잡도	O(log n)
공간복잡도	O(1) (반복), O(log n) (재귀)
적용 조건	정렬된 배열
활용	빠른 탐색, 범위 쿼리

---

다른 탐색과 비교

탐색	시간복잡도	정렬 필요	공간복잡도	특징
선형 탐색	O(n)	불필요	O(1)	단순, 느림
이진 탐색	O(log n)	필요	O(1)	빠름
해시 탐색	O(1)	불필요	O(n)	가장 빠름

---

주의사항

1. 오버플로우 방지

# 잘못된 방법 (오버플로우 가능)
mid = (left + right) // 2
 
# 올바른 방법
mid = left + (right - left) // 2
 
# Python은 임의 정밀도라 문제없지만,
# C/Java 등에서는 중요

2. 종료 조건

# left <= right (일반적)
while left <= right:
    mid = (left + right) // 2
    # ...
 
# left < right (lower/upper bound)
while left < right:
    mid = (left + right) // 2
    # ...

3. 정렬 확인

def binary_search_safe(arr, target):
    # 정렬 확인 (디버깅용)
    if arr != sorted(arr):
        raise ValueError("배열이 정렬되지 않았습니다")
 
    # 이진 탐색 수행
    return binary_search(arr, target)

---

자주 나오는 문제 유형

1. 회전된 배열에서 탐색

문제: 회전된 정렬 배열에서 target 찾기

def search_rotated(arr, target):
    """회전된 정렬 배열 탐색"""
    left = 0
    right = len(arr) - 1
 
    while left <= right:
        mid = (left + right) // 2
 
        if arr[mid] == target:
            return mid
 
        # 왼쪽이 정렬되어 있는 경우
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 오른쪽이 정렬되어 있는 경우
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
 
    return -1
 
# 테스트
arr = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(arr, 0))  # 4
print(search_rotated(arr, 3))  # -1
 
# 시간복잡도: O(log n)

핵심: 절반은 항상 정렬되어 있음

---

2. 최솟값 찾기

문제: 회전된 정렬 배열에서 최솟값 찾기

def find_min_rotated(arr):
    """회전된 배열의 최솟값"""
    left = 0
    right = len(arr) - 1
 
    while left < right:
        mid = (left + right) // 2
 
        # 오른쪽이 더 작으면 오른쪽에 최솟값
        if arr[mid] > arr[right]:
            left = mid + 1
        else:
            right = mid
 
    return arr[left]
 
# 테스트
print(find_min_rotated([4, 5, 6, 7, 0, 1, 2]))  # 0
print(find_min_rotated([3, 4, 5, 1, 2]))        # 1
 
# 시간복잡도: O(log n)

핵심: 중간값과 끝값 비교

---

3. 제곱근 구하기

문제: x의 제곱근 (소수점 버림)

def sqrt(x):
    """이진 탐색으로 제곱근"""
    if x < 2:
        return x
 
    left = 1
    right = x // 2
 
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
 
        if square == x:
            return mid
        elif square < x:
            left = mid + 1
        else:
            right = mid - 1
 
    return right  # 내림
 
# 테스트
print(sqrt(8))   # 2
print(sqrt(16))  # 4
 
# 시간복잡도: O(log n)

핵심: 1부터 x까지 이진 탐색

---

4. 범위 안의 개수 세기

문제: target과 같은 요소의 개수

def count_occurrences(arr, target):
    """target의 개수"""
    first = find_first(arr, target)
 
    if first == -1:
        return 0
 
    last = find_last(arr, target)
    return last - first + 1
 
# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(count_occurrences(arr, 2))  # 3
print(count_occurrences(arr, 6))  # 0
 
# 또는 bisect 사용
import bisect
 
def count_occurrences_bisect(arr, target):
    left = bisect.bisect_left(arr, target)
    right = bisect.bisect_right(arr, target)
    return right - left
 
print(count_occurrences_bisect(arr, 2))  # 3

핵심: upper_bound - lower_bound

---

5. 이진 탐색으로 최적값 찾기

문제: 조건을 만족하는 최솟값/최댓값 찾기

def find_min_satisfying(condition, left, right):
    """조건을 만족하는 최솟값"""
    result = right + 1
 
    while left <= right:
        mid = (left + right) // 2
 
        if condition(mid):
            result = mid
            right = mid - 1  # 더 작은 값 찾기
        else:
            left = mid + 1
 
    return result if result != right + 1 else -1
 
# 예: x^2 >= 100인 최소 x
def condition(x):
    return x * x >= 100
 
print(find_min_satisfying(condition, 0, 100))  # 10
 
# 시간복잡도: O(log n)

핵심: Parametric Search (매개변수 탐색)

---

6. 나무 자르기 (백준 2805)

문제: 적어도 M미터가 되도록 하는 최대 높이

def cut_trees(trees, m):
    """나무 자르기"""
    left = 0
    right = max(trees)
    result = 0
 
    while left <= right:
        mid = (left + right) // 2
 
        # mid 높이로 잘랐을 때 얻는 나무
        total = sum(tree - mid if tree > mid else 0 for tree in trees)
 
        if total >= m:
            result = mid
            left = mid + 1  # 더 높게 자르기
        else:
            right = mid - 1
 
    return result
 
# 테스트
trees = [20, 15, 10, 17]
print(cut_trees(trees, 7))  # 15
 
# 시간복잡도: O(n log H) - H: 최대 높이

핵심: 답의 범위를 이진 탐색

---

7. 공유기 설치 (백준 2110)

문제: 공유기 사이 최대 거리

def install_routers(houses, c):
    """공유기 설치"""
    houses.sort()
 
    left = 1
    right = houses[-1] - houses[0]
    result = 0
 
    while left <= right:
        mid = (left + right) // 2
 
        # mid 거리로 설치 가능한 개수
        count = 1
        last_pos = houses[0]
 
        for house in houses[1:]:
            if house - last_pos >= mid:
                count += 1
                last_pos = house
 
        # c개 이상 설치 가능
        if count >= c:
            result = mid
            left = mid + 1  # 거리 늘리기
        else:
            right = mid - 1
 
    return result
 
# 테스트
houses = [1, 2, 8, 4, 9]
print(install_routers(houses, 3))  # 3
 
# 시간복잡도: O(n log D) - D: 최대 거리

핵심: 거리를 이진 탐색

---

추천 연습 문제

기초

• LeetCode 704 - Binary Search
• LeetCode 35 - Search Insert Position
• 백준 1920번 - 수 찾기

중급

• LeetCode 33 - Search in Rotated Sorted Array
• LeetCode 34 - Find First and Last Position
• LeetCode 69 - Sqrt(x)
• 백준 2805번 - 나무 자르기

고급

• LeetCode 4 - Median of Two Sorted Arrays
• 백준 2110번 - 공유기 설치
• 백준 1300번 - K번째 수

---

이진 탐색 유형 정리

1. 기본 이진 탐색

# 정확한 값 찾기
while left <= right:
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid

2. Lower/Upper Bound

# 이상/초과 위치 찾기
while left < right:
    mid = (left + right) // 2
    if arr[mid] < target:  # 또는 <=
        left = mid + 1
    else:
        right = mid

3. Parametric Search

# 조건을 만족하는 최대/최소값
while left <= right:
    mid = (left + right) // 2
    if condition(mid):
        result = mid
        # 더 좋은 값 찾기
    else:
        # 범위 조정

---

언제 사용할까?

사용 가능

• 정렬된 배열: 전제 조건
• 대용량 데이터: O(log n) 필요
• 범위 쿼리: lower/upper bound
• 최적값 찾기: parametric search

사용 불가

• 비정렬 데이터: 선형 탐색 또는 해시
• 빈번한 삽입/삭제: BST 또는 해시
• 작은 데이터: 선형 탐색도 충분

결론: 정렬된 대용량 데이터 탐색의 최적 알고리즘!