Binary Search (이진 탐색)
📝 개념 정의
정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
핵심:
- 시작점, 끝점, 중간점 사용
- 탐색 범위를 절반씩 축소
- 정렬된 데이터 필수
🆚 순차 탐색 vs 이진 탐색
순차 탐색 (Sequential Search)
앞에서부터 하나씩 확인
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
↑ ↑ ↑ ↑ ← 순차적으로 확인
시간 복잡도: O(N)
이진 탐색 (Binary Search)
중간점 기준으로 절반씩 제거
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
↑
중간점
시간 복잡도: O(log N)
🔍 이진 탐색 과정
예시: 4 찾기
배열: [0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
Step 1
시작점: 0, 끝점: 9, 중간점: 4
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
↑
중간점(8)
4 < 8 → 왼쪽 탐색
Step 2
시작점: 0, 끝점: 3, 중간점: 1
[0, 2, 4, 6]
↑
중간점(2)
4 > 2 → 오른쪽 탐색
Step 3
시작점: 2, 끝점: 3, 중간점: 2
[4, 6]
↑
중간점(4)
4 == 4 → 탐색 완료!
⏱️ 시간 복잡도
분석
단계마다 탐색 범위를 2로 나눔
| 단계 | 범위 | |------|------| | 0 | n | | 1 | n/2 | | 2 | n/4 | | k | n/2^k |
n/2^k = 1 → k = log₂n
시간 복잡도: O(log N)
💻 구현 방법
1. 순환 호출 (Recursive)
int binarySearch1(int key, int low, int high) {
int mid;
if(low <= high) {
mid = (low + high) / 2;
if(key == arr[mid]) {
return mid; // 탐색 성공
} else if(key < arr[mid]) {
// 왼쪽 부분 탐색
return binarySearch1(key, low, mid-1);
} else {
// 오른쪽 부분 탐색
return binarySearch1(key, mid+1, high);
}
}
return -1; // 탐색 실패
}
2. 반복 구조 (Iterative)
int binarySearch2(int key, int low, int high) {
int mid;
while(low <= high) {
mid = (low + high) / 2;
if(key == arr[mid]) {
return mid;
} else if(key < arr[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1; // 탐색 실패
}
🎯 Parametric Search (파라메트릭 서치)
개념
최적화 문제를 결정 문제로 바꾸어 해결하는 기법
특징:
- "예" 또는 "아니오"로 답변
- 이진 탐색 활용
- 최적값 빠르게 찾기
예제: 떡볶이 떡 만들기
문제:
- 떡의 높이:
[19, 14, 10, 17] - 절단기 높이 H 설정
- 손님이 요청한 길이 M = 6
- H의 최댓값은?
절단기 높이 15cm:
19 → 15 (잘린 길이: 4)
14 → 14 (잘린 길이: 0)
10 → 10 (잘린 길이: 0)
17 → 15 (잘린 길이: 2)
총 잘린 길이: 4 + 0 + 0 + 2 = 6 ✅
해결 아이디어
이진 탐색 활용
- 탐색 범위: 0 ~ 최대 높이
- 중간점 H로 자르기
- 잘린 떡 길이 확인
- M 이상: 시작점 = 중간점 + 1
- M 미만: 끝점 = 중간점 - 1
- 반복
Step 1
시작점: 0, 끝점: 19, 중간점: 9
H = 9로 자르기
잘린 길이: 10 + 5 + 1 + 8 = 24
24 > 6 → 시작점 = 10
Step 2
시작점: 10, 끝점: 19, 중간점: 14
H = 14로 자르기
잘린 길이: 5 + 0 + 0 + 3 = 8
8 > 6 → 시작점 = 15
Step 3
시작점: 15, 끝점: 19, 중간점: 17
H = 17로 자르기
잘린 길이: 2 + 0 + 0 + 0 = 2
2 < 6 → 끝점 = 16
Step 4
시작점: 15, 끝점: 16, 중간점: 15
H = 15로 자르기
잘린 길이: 4 + 0 + 0 + 2 = 6
6 == 6 → 답: 15
📊 이진 탐색 vs 순차 탐색
| 특징 | 순차 탐색 | 이진 탐색 | |------|-----------|-----------| | 정렬 | 불필요 | 필수 | | 시간 | O(N) | O(log N) | | 구현 | 간단 | 보통 | | 적용 | 작은 데이터 | 큰 데이터 |
💡 이진 탐색 사용 시기
✅ 데이터가 정렬되어 있을 때 ✅ 데이터 양이 많을 때 ✅ 탐색 범위가 큰 문제 (예: 0 ~ 10억) ✅ Parametric Search 문제
❓ 면접 질문 예시
Q1. 이진 탐색이란 무엇인가요?
답변: 정렬된 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다. 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정하고, 찾고자 하는 값과 중간점을 비교하여 탐색 범위를 절반으로 줄여나갑니다. 시간 복잡도는 O(log N)입니다.
Q2. 이진 탐색의 시간 복잡도는?
답변: O(log N)입니다. 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log N에 비례합니다. 예를 들어 데이터 개수가 32개일 때, 1단계를 거치면 16개, 2단계를 거치면 8개, 3단계를 거치면 4개로 줄어듭니다.
Q3. 이진 탐색의 전제 조건은?
답변: 데이터가 정렬되어 있어야 합니다. 정렬되지 않은 데이터에서는 중간점을 기준으로 왼쪽과 오른쪽을 나눌 수 없기 때문에 이진 탐색을 사용할 수 없습니다. 정렬되지 않은 경우 순차 탐색을 사용해야 합니다.
Q4. Parametric Search란 무엇인가요?
답변: 최적화 문제를 결정 문제로 바꾸어 해결하는 기법입니다. 특정 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 문제에서 "예" 또는 "아니오"로 답변할 수 있도록 변환하여 이진 탐색으로 해결합니다. 코딩 테스트에서 탐색 범위가 큰 문제는 이진 탐색을 떠올려야 합니다.
Q5. 순환 호출과 반복 구조 중 어떤 것이 좋나요?
답변: 반복 구조가 일반적으로 더 효율적입니다. 순환 호출은 함수 호출 오버헤드가 있고 스택 메모리를 사용하여 깊이가 깊어지면 스택 오버플로우가 발생할 수 있습니다. 반복 구조는 메모리 효율적이고 속도도 빠릅니다. 하지만 순환 호출이 코드가 더 간결하고 이해하기 쉬울 수 있습니다.
📚 원본 참고 자료
출처: 2023-CS-Study
- 링크: algorithm_binary_search.md
- 내용: 이진 탐색, 시간 복잡도, Parametric Search