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

이진 탐색 알고리즘이란?

이진 탐색 알고리즘 특징

• 전제 조건: 데이터가 반드시 정렬되어 있어야 함

• 시간 복잡도: 매 탐색마다 탐색 범위를 절반으로 줄이므로 **O(log N)**의 시간복잡도를 가짐

• 정확성: 필요한 값이 정확히 있는 위치를 찾아냄

• 낮은 시간 비용: 순차 탐색보다 훨씬 빠름 (특히 데이터가 클 때 유리)

이진 탐색 알고리즘 실제 적용 사례

• 정렬된 배열에서 특정 값 찾기

• 검색 기능 구현: 예) 사전, DB 인덱스, 이분 탐색 기반 검색

• 최솟값/최댓값을 구하는 최적화 문제: 파라메트릭 서치 (ex: 최소 배달 시간 찾기)

• 탐색 범위를 좁혀가며 정답을 찾는 문제 (ex: 백준 2110 공유기 설치)

이 탐색 알고리즘의 단계

이진 탐색 구현 (ex. python)

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid  # target found
        elif arr[mid] < target:
            left = mid + 1  # search right half
        else:
            right = mid - 1  # search left half
    
    return -1  # not found

선형 탐색 vs. 이진 탐색 비교