[알고리즘 이론] 이진 탐색(Binary Search)

이진 탐색(Binary Search) 완벽 정리 🔍

안녕하세요! 오늘은 프로그래밍에서 가장 기본적이면서도 중요한 알고리즘 중 하나인 **이진 탐색(Binary Search)**에 대해 알아보겠습니다. 이진 탐색은 "이분 탐색"이라고도 불리며, 코딩 테스트에서도 자주 출제되는 핵심 알고리즘입니다.

🤔 이진 탐색이 뭔가요?

이진 탐색은 정렬된 배열에서 특정 값을 빠르게 찾는 방법입니다.

예를 들어 사전에서 단어를 찾을 때를 생각해보세요. 'S'로 시작하는 단어를 찾는다면, 처음부터 한 페이지씩 넘기지 않고 대략 중간쯤을 펼쳐서 확인한 다음, 그보다 앞쪽인지 뒤쪽인지 판단해서 범위를 좁혀나가죠? 바로 그 원리입니다!

⚡ 왜 이진 탐색을 써야 할까요?

속도 비교

일반적인 순차 탐색 vs 이진 탐색을 비교해보겠습니다:

📊 1,000,000개 데이터에서 특정 값 찾기

탐색 방법	최대 비교 횟수	시간 복잡도
순차 탐색	1,000,000번	O(n)
이진 탐색	20번	O(log n)

차이가 엄청나죠? 이것이 바로 이진 탐색의 힘입니다! 💪

🔧 이진 탐색은 어떻게 작동하나요?

동작 원리

1. 배열의 가운데 값을 확인합니다
2. 찾는 값과 비교합니다:
   • 가운데 값 == 찾는 값 → 🎉 찾았습니다!
   • 가운데 값 > 찾는 값 → 왼쪽 절반에서 계속 찾습니다
   • 가운데 값 < 찾는 값 → 오른쪽 절반에서 계속 찾습니다
3. 범위를 좁혀가며 반복합니다

실제 예시로 이해하기

배열 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]에서 13을 찾아보겠습니다:

🎯 13을 찾아보자!

1단계: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
              ↑
          가운데 값: 9
          9 < 13 → 오른쪽으로!

2단계: [11, 13, 15, 17, 19]
              ↑
          가운데 값: 15
          15 > 13 → 왼쪽으로!

3단계: [11, 13]
              ↑
          가운데 값: 13
          13 == 13 → 🎉 찾았다!

💻 코드로 구현해보기

Python 기본 구현

def binary_search(arr, target):
    """
    이진 탐색 함수
    - arr: 정렬된 리스트
    - target: 찾을 값
    - 반환: 찾은 인덱스 (없으면 -1)
    """
    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  # 못 찾음

# 테스트해보기
numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
result = binary_search(numbers, 13)
print(f"13의 위치: {result}")  # 출력: 6

재귀 버전도 만들어보기

def binary_search_recursive(arr, target, left=0, right=None):
    """재귀로 구현한 이진 탐색"""
    if right is None:
        right = len(arr) - 1
    
    # 더 이상 찾을 범위가 없음
    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)

⚠️ 주의할 점들

1. 정렬된 배열에서만 사용 가능!

# ❌ 틀린 예시
unsorted_arr = [3, 1, 4, 1, 5, 9]
result = binary_search(unsorted_arr, 4)  # 예상과 다른 결과!

# ✅ 올바른 예시
sorted_arr = [1, 1, 3, 4, 5, 9]
result = binary_search(sorted_arr, 4)  # 정확한 결과

2. 중간값 계산할 때 오버플로우 조심

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

# ✅ 안전한 계산
mid = left + (right - left) // 2

3. 경계 조건 체크

# left <= right 조건을 빼먹으면 안 됩니다!
while left <= right:  # <= 중요!

🚀 이진 탐색의 변형들

1. 첫 번째 위치 찾기 (Lower Bound)

중복된 값이 있을 때 가장 첫 번째 위치를 찾고 싶다면:

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

# 테스트
arr = [1, 2, 2, 2, 3, 4, 5]
print(find_first_position(arr, 2))  # 출력: 1 (첫 번째 2의 위치)

2. 마지막 위치 찾기 (Upper Bound)

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

🌟 실전에서 이진 탐색 활용하기

1. 제곱근 구하기

def sqrt_binary_search(n):
    """이진 탐색으로 제곱근 구하기"""
    if n < 1:
        return 0
    
    left, right = 1, n
    
    while left <= right:
        mid = (left + right) // 2
        square = mid * mid
        
        if square == n:
            return mid
        elif square < n:
            left = mid + 1
        else:
            right = mid - 1
    
    return right  # 가장 가까운 정수값

print(sqrt_binary_search(16))  # 출력: 4
print(sqrt_binary_search(15))  # 출력: 3

2. 특정 값 이상인 첫 번째 위치 찾기

def find_ceiling(arr, target):
    """target 이상인 첫 번째 값의 위치"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left if left < len(arr) else -1

📈 성능 분석

상황 시간 복잡도 설명

최선의 경우	O(1)	첫 번째 비교에서 바로 찾음
평균적인 경우	O(log n)	대부분의 경우
최악의 경우	O(log n)	끝까지 찾아야 하는 경우

공간 복잡도:

• 반복문 버전: O(1)
• 재귀 버전: O(log n) - 호출 스택 때문

🎓 언제 이진 탐색을 사용하면 좋을까요?

✅ 이진 탐색을 사용하면 좋은 경우:

• 정렬된 대용량 데이터에서 검색
• 데이터베이스 인덱스 구현
• 게임에서 점수 순위 찾기
• 최적화 문제 (parametric search)

❌ 이진 탐색이 적합하지 않은 경우:

• 정렬되지 않은 데이터
• 데이터가 자주 변경되는 경우
• 작은 크기의 배열 (오버헤드가 더 클 수 있음)

🔥 코딩 테스트 팁

1. 정렬 여부 항상 확인하기
2. 경계 조건 꼼꼼히 테스트하기
3. 오버플로우 방지하기
4. 변형 문제 패턴 익혀두기

마무리

이진 탐색은 프로그래밍의 기초이면서도 매우 강력한 도구입니다. 단순해 보이지만 정확히 구현하려면 주의할 점들이 많아서, 충분한 연습이 필요합니다.

핵심 포인트 정리:

• ✅ 정렬된 데이터에서만 사용
• ✅ O(log n)의 뛰어난 성능
• ✅ 다양한 변형 문제에 응용 가능
• ✅ 구현은 간단하지만 디테일이 중요

이제 직접 구현해보고, 다양한 문제에 적용해보세요! 익숙해지면 정말 유용한 도구가 될 거예요. 😊

---

이 글이 도움이 되셨다면 좋아요와 댓글 부탁드려요! 궁금한 점이 있으시면 언제든 질문해주세요. 💬