이분 탐색(Binary Search) 알고리즘

개요

이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾을 때 사용하는 효율적인 탐색 알고리즘이다.
탐색 범위를 절반씩 줄여나가면서 값을 찾기 때문에, 시간 복잡도는 $O(\log n)$ 으로 매우 빠른 속도를 보인다.

동작 원리

1. 배열이 정렬되어 있어야 한다.
2. 배열의 가운데 값(mid) 을 선택한다.
3. 찾고자 하는 값과 가운데 값을 비교한다.
   • 찾고자 하는 값이 가운데 값보다 작으면 왼쪽 부분을 탐색한다.
   • 찾고자 하는 값이 가운데 값보다 크면 오른쪽 부분을 탐색한다.
   • 찾고자 하는 값이 가운데 값과 같으면 탐색을 종료한다.
4. 위 과정을 반복하면서 범위를 절반씩 줄여 나간다.

구현 방법

이분 탐색은 크게 두 가지 방식으로 구현할 수 있다.

1. 반복문(Iterative) 방식
2. 재귀(Recursive) 방식

---

1. 반복문(Iterative) 방식

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  # 값이 없는 경우

✅ 반복문 방식 특징

• 반복문을 사용하여 이분 탐색을 구현.
• while문을 통해 탐색 범위를 줄여나감.
• 시간 복잡도는 $O(\log n)$.

---

2. 재귀(Recursive) 방식

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]
target = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(result)  # 출력: 3

✅ 재귀 방식 특징

• 함수가 자기 자신을 호출하면서 탐색 범위를 줄여나감.
• 코드가 직관적이지만 스택 메모리를 사용하므로 반복문 방식보다 메모리 소모가 클 수 있음.
• 시간 복잡도는 $O(\log n)$.

---

📌 이분 탐색의 시간 복잡도 분석

• 탐색 범위를 절반으로 줄이는 과정이 최대 $\log_2 n$ 번 반복됨.
• 따라서, 시간 복잡도는 $O(\log n)$.

데이터 개수($n$)	선형 탐색($O(n)$)	이분 탐색($O(\log n)$)
10	10	4
100	100	7
1,000	1,000	10
1,000,000	1,000,000	20

➡️ 선형 탐색($O(n)$)에 비해 이분 탐색($O(\log n)$)은 매우 빠르게 작동한다.

---

📌 이분 탐색의 조건과 한계

✅ 조건

1. 배열이 반드시 정렬되어 있어야 한다.
2. 중복 값이 있는 경우 특정 인덱스가 반환될 수 있다. (첫 번째 또는 마지막 위치를 찾는 경우 추가 로직이 필요)

❌ 한계

1. 정렬이 안 된 배열에서는 사용할 수 없다. (정렬 과정이 필요하며, 정렬 자체가 $O(n \log n)$이므로 추가 비용이 발생함.)
2. 데이터가 작은 경우 굳이 사용하지 않아도 됨. (작은 배열에서는 선형 탐색($O(n)$)이 더 간단할 수도 있음.)

---

📌 응용 예시

이분 탐색은 탐색 문제 뿐만 아니라 최적화 문제에도 응용될 수 있다.

1. 정렬된 배열에서 특정 값 찾기

이분 탐색의 기본 활용법으로, 정렬된 배열에서 원하는 값을 빠르게 찾는 데 사용된다.

2. Lower Bound / Upper Bound 탐색

• Lower Bound: 찾고자 하는 값 이상이 처음 등장하는 위치 찾기
• Upper Bound: 찾고자 하는 값보다 큰 값이 처음 등장하는 위치 찾기
• bisect 모듈을 활용하면 쉽게 구현 가능하다.

import bisect

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

lower = bisect.bisect_left(arr, target)  # 3이 처음 등장하는 위치
upper = bisect.bisect_right(arr, target)  # 3보다 큰 값이 처음 등장하는 위치

print(lower)  # 출력: 1
print(upper)  # 출력: 3

3. 최적화 문제 해결 (Parametric Search)

• 예제: 특정 조건을 만족하는 값 중 최소/최대값을 찾을 때 활용.
• 예시 문제: "n개의 나무가 있을 때, 원하는 길이만큼 나무를 얻기 위해 절단기의 높이를 얼마로 설정해야 하는가?"
  (높이를 설정하면 얻을 수 있는 나무 길이가 변하므로, 최적의 높이를 이분 탐색으로 찾을 수 있다.)

---

📌 정리

항목	설명
시간 복잡도	$O(\log n)$
필수 조건	배열이 정렬되어 있어야 함
반복문 vs 재귀	반복문 방식이 더 메모리 효율적
활용 분야	탐색, 최적화 문제, Parametric Search

이분 탐색은 빠른 탐색이 필요한 경우 필수적으로 사용되는 알고리즘이다.
다양한 문제 해결에 응용되므로 확실히 익혀두면 많은 도움이 된다! 🚀