알고리즘
Binary Search
다른 이름: 이진 탐색 , 이분 탐색
정의
정렬된 배열에서 O(log n) 시간복잡도로 값을 찾는 탐색 알고리즘. 중간값(mid)과 비교 후 탐색 범위를 절반씩 줄임. Lower Bound(이상), Upper Bound(초과), 파라메트릭 서치(최적화→결정 문제 변환) 응용. 정렬 필수
상세 설명
기술 스펙
- 시간복잡도: O(log n) - 매번 탐색 범위 절반 감소
- 공간복잡도: O(1) - 반복문 구현, O(log n) - 재귀 구현
- 전제 조건: 배열이 정렬되어 있어야 함
- Lower Bound: target 이상인 첫 위치 (C++ lower_bound)
- Upper Bound: target 초과인 첫 위치 (C++ upper_bound)
- 파라메트릭 서치: "최소화/최대화" → "X 이하/이상 가능?" 결정 문제
- 실수 이진 탐색: 오차 범위(1e-9) 내에서 반복
실무 활용
- 정렬 배열 탐색: 1억 개 데이터에서 27회 비교로 찾기
- 중복값 범위: lower_bound ~ upper_bound로 개수 계산
- 파라메트릭 서치: 백준 1654 (랜선 자르기), 2110 (공유기 설치)
- STL: std::binary_search, lower_bound, upper_bound
- 이분 답안 탐색: 최소/최대 비용, 시간 찾기
장점
- 매우 빠름: O(log n) - 선형 탐색 O(n) 대비 압도적
- 간단한 구현: 반복문 10줄 내외
- 안정적 성능: 최악의 경우도 O(log n)
- 응용 다양: Lower/Upper Bound, 파라메트릭 서치
단점 및 제약
- 정렬 필수: 정렬 비용 O(n log n) 추가
- 랜덤 액세스: 연결 리스트 등 불가
- 중간값 오버플로우: mid = (left + right) / 2 → left + (right - left) / 2
- 부동소수점: 실수 비교 시 오차 처리 필요
호환성
모든 정렬 가능 자료구조. C++ STL, Python bisect, Java Arrays.binarySearch
표준 정보
표준화 기구: 알고리즘 교과서 표준. ACM ICPC, 코딩 테스트 필수
출시 연도: 1946년