이진 탐색(Binary Search)은 정렬된 배열에서 목표값을 O(log n)에 찾는 알고리즘이다. 배열의 중간값을 기준으로 탐색 범위를 절반씩 줄여나가며, 선형 탐색 O(n)보다 압도적으로 빠르다.
동작 원리
정렬된 배열: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
찾는 값: 23
인덱스: 0 1 2 3 4 5 6 7 8 9
1단계: left=0, right=9 → mid=4 → arr[4]=16 < 23 → left=5
2단계: left=5, right=9 → mid=7 → arr[7]=56 > 23 → right=6
3단계: left=5, right=6 → mid=5 → arr[5]=23 = 23 → 발견!
총 3번 비교 (선형 탐색이라면 최대 6번)
시간 복잡도
| 경우 | 복잡도 |
|---|
| 최선 | O(1) — 중간값이 정답 |
| 평균/최악 | O(log n) |
n=1,000,000이면 최대 20번 비교만으로 탐색 완료.
코드 구현
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
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 없음
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(binary_search(arr, 23)) # 5
print(binary_search(arr, 99)) # -1
java
// Java — Arrays.binarySearch 내장 지원
int[] arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int idx = Arrays.binarySearch(arr, 23); // 5
python
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)
이진 탐색 응용
Lower Bound / Upper Bound
python
import bisect
arr = [1, 2, 2, 2, 3, 4]
bisect.bisect_left(arr, 2) # 1 — 2가 처음 등장하는 위치
bisect.bisect_right(arr, 2) # 4 — 2 다음에 삽입할 위치
파라메트릭 서치 (Parametric Search)
"최솟값 중 조건을 만족하는 값 찾기" 유형에 이진 탐색 적용.
예: "떡을 H 높이로 자를 때 필요한 떡의 합이 M 이상이 되는 최대 H"
→ H의 범위에 이진 탐색 적용
선형 탐색 vs 이진 탐색
| n | 선형 탐색 O(n) | 이진 탐색 O(log n) |
|---|
| 100 | 100번 | 7번 |
| 10,000 | 10,000번 | 14번 |
| 1,000,000 | 1,000,000번 | 20번 |
단, 이진 탐색은 반드시 정렬된 배열이 필요하다.
이진 탐색 변형 (Lower/Upper Bound)
단순 탐색 외에 "경계값 찾기"에 이진 탐색을 활용한다.
lower_bound(arr, x): x 이상인 첫 번째 위치 반환
upper_bound(arr, x): x 초과인 첫 번째 위치 반환
예시: arr = [1, 2, 2, 3, 4], x = 2
lower_bound → index 1 (처음 2가 있는 위치)
upper_bound → index 3 (2를 초과하는 첫 위치)
활용: 정렬 배열에서 특정 값의 범위, 삽입 위치, 중복 원소 개수 계산.
이진 탐색 응용 패턴
이진 탐색은 "monotone function(단조 함수) 위에서 전환점 찾기"에 범용적으로 사용된다.
Parametric Search (매개변수 탐색):
- 문제: "최솟값이 최대가 되도록 하는 조건"
- 방법: 답을 binary search로 가정하고, 그 값이 가능한지 O(n)으로 검증
- 예: 블루레이 용량 최소화, 나무 자르기
관련 개념
- •이진 트리 — 이진 탐색 트리(BST)의 기반 자료구조
- •해시맵 — O(1) 검색의 대안 자료구조
- •정렬 알고리즘 — 이진 탐색을 위한 사전 정렬 필요
참고문헌
- •Cormen et al. Introduction to Algorithms — Chapter 2
- •Knuth. The Art of Computer Programming, Vol. 3
