8. 이진 탐색은 못 찾았을 때의 답도 정한다
해설글
작성 · 4분 읽기 · 조회수 —수정
기초 개념과 예제를 보강하고 시리즈 흐름을 연결
비어 있는 Dictionary 아래의 세 코드
탐색은 찾으려는 값인 key가 자료 안에 있는지, 있다면 어디에 있는지 찾는 작업이다. 선형 탐색은 앞에서부터 하나씩 비교해 정렬되지 않은 배열에서도 동작하지만 최악에는 모든 원소를 본다. 이진 탐색은 오름차순으로 정렬된 배열에서 중간값과 key를 비교해 답이 있을 수 없는 절반을 버린다.
예를 들어 [1, 3, 5, 7, 9]에서 7을 찾을 때 중간값 5보다 key가 크므로 왼쪽의 1, 3, 5는 더 볼 필요가 없다. 남은 [7, 9]에서 다시 중간을 고른다. 입력이 정렬되지 않았다면 “왼쪽은 모두 더 작다”는 근거가 사라져 같은 방식으로 버릴 수 없다.
Dictionary는 key로 값을 찾는 추상 자료형이다. 배열로 구현할 수도, 트리나 해시 테이블로 구현할 수도 있다. 이 글에서는 정렬 배열 위에서 key의 위치나 삽입 경계를 찾는 이진 탐색에 범위를 좁힌다.
6주차 노트에는 비교 정렬의 하한을 정리한 다음 Dictionary라는 제목만 남아 있다. 설명은 거의 비어 있지만 저장소에는 이진 탐색 코드 세 개가 있다. 하나는 재귀 탐색, 하나는 lower bound, 하나는 Y/N 답으로 구간을 줄이는 문제다.
세 코드를 나란히 읽으니 이진 탐색에서 먼저 정할 것은 mid 공식보다 반환값의 의미였다. 찾는 값이 배열 안에 있을 때만 생각하면 코드들이 비슷해 보인다. 값이 없거나 중복될 때는 서로 다른 문제를 푼다.
같은 배열에서 달라지는 계약
정렬 배열 A = [1, 3, 3, 7]을 기준으로 세 계약을 구분해 보자.
| 함수 계약 | 성공 또는 실패의 의미 | k=3 | k=4 | k=0 | k=8 |
|---|---|---|---|---|---|
| exact search | 같은 값의 인덱스, 없으면 -1 | 1 또는 2 | -1 | -1 | -1 |
| predecessor | A[i] <= k인 마지막 인덱스, 없으면 -1 |
2 | 2 | -1 | 3 |
| lower bound | A[i] >= k인 첫 인덱스, 없으면 n |
1 | 3 | 0 | 4 |
1013-1.c는 값이 같으면 바로 인덱스를 반환하지만 탐색 구간이 비면 r을 반환한다. 흔한 exact search의 -1과 다르며 predecessor 결과와 닮았다. 다만 값을 찾았을 때는 중복 중 아무 위치나 즉시 반환하므로 완전한 predecessor 함수도 아니다. 과제 명세가 남아 있지 않아 이 혼합된 반환이 의도였는지는 확정할 수 없다.
1013-2.c는 첫 A[i] >= k를 찾는다. 값이 없을 때 n을 반환하는 것은 오류 표시가 아니다. k를 정렬 순서를 유지하며 삽입할 위치가 배열 끝이라는 뜻이다.
lower bound가 지키는 두 구간
이번 재현 구현은 반열린 구간 [left, right)를 사용한다. 왼쪽 끝 left는 포함하고 오른쪽 끝 right는 포함하지 않는다는 뜻이다. 원소가 4개인 배열 전체는 [0, 4)로 적으며, 실제로 읽을 수 있는 인덱스는 0, 1, 2, 3이다. left == right이면 남은 원소가 없는 빈 구간이다.
int lower_bound(const int *a, int n, int key) {
int left = 0;
int right = n;
while (left < right) {
int mid = left + (right - left) / 2;
if (a[mid] < key) left = mid + 1;
else right = mid;
}
return left;
}
반복 중 left보다 앞의 원소는 모두 key보다 작고, right부터 뒤의 원소는 모두 key 이상이다. left..right-1만 아직 답 후보로 남는다. a[mid] < key이면 mid까지는 답일 수 없어 left=mid+1로 버린다. 반대로 a[mid] >= key이면 mid가 답일 가능성이 있으므로 mid를 버리지 않고 right=mid로 둔다.
이 두 번째 대입이 중복에서 중요하다. [1, 3, 3, 7], key=3을 추적하면 처음 mid=2, 값은 3이다. 답 후보이므로 right=2가 된다. 다음 mid=1도 3이라 right=1이 된다. 아직 left=0이므로 한 번 더 비교한다. mid=0의 값 1은 3보다 작아 left=1이 되고, 이제 left=right=1에서 끝나 첫 번째 3의 위치 1을 반환한다. 같은 값을 찾았다고 즉시 끝냈다면 인덱스 2가 나와 lower bound 계약을 어겼다.
key=4에서는 처음 mid=2의 3이 작아 left=3이 된다. 다음 mid=3의 7은 크므로 right=3이 되고 답은 3이다. key=8이면 모든 원소가 작은 구간으로 들어가 left=n에서 끝난다. 빈 배열도 처음부터 left=right=0이라 안전하게 0을 반환한다.
실패값도 정상적인 답이다
predecessor는 반대 방향의 경계를 찾는다. A[mid] <= key이면 mid를 포함해 더 오른쪽을 찾아야 하므로 left=mid+1, 크면 right=mid-1로 옮긴다. 종료 후 right가 마지막 <= key 위치다. 최솟값보다 작은 key에서는 right=-1이 된다.
이번 재현 코드는 빈 배열과 작은 비감소 배열들을 만들고 각 key에 대해 선형 탐색 결과와 exact, predecessor, lower bound를 대조한다. 중복, 없는 중간값, 양 끝 바깥값도 포함하며 Sanitizer 실행에서 binary-search contracts: ok를 확인했다.
이진 탐색은 후보 구간을 절반으로 줄여 O(log n)에 동작한다. 그러나 빠른 반복문만으로 함수가 완성되는 것은 아니다. 못 찾았을 때 -1을 줄지, 앞 원소를 줄지, 삽입 위치를 줄지를 먼저 정해야 성공 조건과 경계 대입도 함께 결정된다.
참고한 기록과 코드
- 개인 노트 「6주차 - Dictionary(사전 , 선형탐색 & 이진탐색)」, 2025-10-13
Week6 Dictionary/1013-1.cWeek6 Dictionary/1013-2.c