[Python - 알고리즘] 이분탐색

이분탐색(Binary Search) 완벽 정리 + 코드 한 줄 주석

1. 이분탐색이란?

정렬된 데이터에서 원하는 값을 빠르게 찾는 탐색 알고리즘입니다.
데이터를 반씩 나누며 범위를 좁혀가서 찾기 때문에 효율적입니다.

2. 시간복잡도 비교

탐색 방법	시간복잡도	설명
선형 탐색	O(N)	하나씩 차례대로 찾음
이분탐색	O(log N)	중간값 기준 반씩 탐색 범위 축소

3. 이분탐색 원리

1. 데이터가 정렬되어 있어야 합니다.
2. 중간값을 기준으로 찾는 값과 비교
3. 찾는 값이 중간값보다 크면 왼쪽 절반 버리고 오른쪽 탐색
4. 찾는 값이 중간값보다 작으면 오른쪽 절반 버리고 왼쪽 탐색
5. 값이 일치하면 탐색 종료

4. 예시

data = [1, 3, 5, 7, 9, 11, 13]
find_num = 9

1) 중간값 7 (인덱스 3)
   9 > 7 → 왼쪽 절반 버림 → [9, 11, 13]

2) 중간값 11 (인덱스 5)
   9 < 11 → 오른쪽 절반 버림 → [9]

3) 중간값 9 (인덱스 4)
   찾음!

5. 기본 이분탐색 함수 구현

def binary_search(arr, target):
    left, right = 0, 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 반환

6. Lower Bound 함수 구현

def lower_bound(arr, target):
    left, right = 0, len(arr)       # 탐색 범위는 0부터 배열 길이까지 (right는 len(arr)으로 설정)

    while left < right:              # left가 right보다 작을 동안 반복
        mid = (left + right) // 2   # 중간 인덱스 계산

        if arr[mid] < target:        # 중간값이 타겟보다 작으면
            left = mid + 1          # 왼쪽 부분 버리고 오른쪽 탐색

        else:
            right = mid             # 중간값이 타겟 이상이면 오른쪽 범위를 줄임

    return left                     # 조건을 만족하는 최소 인덱스 반환

7. 응용 예시: 톱날 높이 문제 (나무 자르기)

def cut_wood(woods, height):
    # 톱날 높이(height)로 자를 때 얻는 나무 길이 합 계산
    return sum((w - height) if w > height else 0 for w in woods)

def wood_saw(woods, M):
    left, right = 0, max(woods)    # 톱날 높이의 최소, 최대 범위 설정
    result = 0                     # 결과값 초기화

    while left <= right:            # 탐색 범위가 유효할 동안 반복
        mid = (left + right) // 2  # 중간 톱날 높이 계산
        if cut_wood(woods, mid) >= M:  # mid 높이로 자른 나무가 M 이상이면
            result = mid           # 현재 mid를 결과로 저장