이진 탐색
개요
이진 탐색(binary search)은 정렬된 구간에서 중간 원소를 비교해 답이 놓일 수 없는 절반을 한 번에 버리는 탐색 방법이다. 오름차순으로 정리된 사원 명부에서 특정 이름을 찾을 때 첫 장부터 한 줄씩 읽는 대신 가운데를 펼쳐 앞쪽과 뒤쪽 중 한쪽을 통째로 건너뛰는 방식과 같다.
연혁
John Mauchly는 1946년 무어 스쿨 강의(Moore School Lectures)에서 정렬된 표를 절반씩 좁혀 찾는 이진 탐색을 처음 체계적으로 언급했다. 초기 구현은 배열 길이가 형태일 때만 깔끔하게 맞아떨어졌으나, 1960년 Derrick H. Lehmer가 임의 길이 배열에 동작하는 일반 절차를 발표했고 1962년 Hermann Bottenbruch는 루프 내부의 동등 비교를 끝까지 미루어 매 단계 비교 횟수를 줄인 변형을 제시했다.1
Jon Bentley는 1983년 「Writing Correct Programs」에서 숙련된 프로그래머조차 경계 조건에서 자주 틀리는 사례로 이진 탐색을 꼽으며, 초기 조건·루프 불변식·종료 조건을 분리해 정확성을 검증했다.2 2006년에는 Joshua Bloch가 자신이 작성했던 Java 표준 라이브러리(java.util.Arrays.binarySearch) 구현에서도 양 끝 인덱스를 더하는 (low + high) / 2 계산이 큰 배열에서 부호 있는 32비트 정수 오버플로를 일으킨다는 사실을 공개했다.3
반열린 구간과 루프 불변식
중복된 값이 섞여 있거나 찾는 값이 배열에 없을 때에도 흔들리지 않으려면, 단순히 "같은 값이 있는가" 대신 "target 이상인 값이 처음 나타나는 위치"를 구하는 편이 다루기 쉽다. 이 위치를 왼쪽 삽입 경계(lower bound)라 부른다. 중복 원소가 여러 개면 그중 첫 인덱스를 가리키고, 찾는 값이 없으면 정렬 순서를 깨지 않고 끼워 넣을 자리다. 모든 원소가 target보다 작다면 경계는 배열 끝 바깥인 이 된다.
아직 조사할 원소는 왼쪽 끝 를 포함하고 오른쪽 끝 를 제외하는 반열린 구간 에 둔다. 처음에는 의 모든 원소를 조사 대상으로 삼는다. 삽입 경계 자체의 후보 위치는 양 끝을 포함해 부터 까지이며, 반복 중에도 를 유지한다. 다음 식은 구간 밖의 값과 중간 인덱스가 만족하는 조건이다.
인 동안에는 항상 가 성립한다. 이면 역시 답이 될 수 없으므로 로 올리고, 이면 가 첫 경계일 가능성이 남으므로 로 줄인다. 두 경우 모두 구간 길이 가 반드시 감소하므로 무한 루프 없이 에서 멈춘다.
실행 예제
C++20
C++20에서는 오름차순 정수 배열을 const 참조로 받아 복사 없이 읽는다. lowerBound는 삽입 경계를, indexOfSorted는 실제 일치 위치 또는 -1을 반환하며, 아래 TypeScript판과 같은 세 결과를 출력한다.
#include <cstddef>
#include <iostream>
#include <vector>
std::size_t lowerBound(const std::vector<int>& values, int target) {
std::size_t lo = 0;
std::size_t hi = values.size();
// lo 앞의 값은 target 미만, hi부터의 값은 target 이상이다.
while (lo < hi) {
const auto mid = lo + (hi - lo) / 2;
if (values[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
std::ptrdiff_t indexOfSorted(const std::vector<int>& values, int target) {
const auto index = lowerBound(values, target);
// 배열 끝의 삽입 경계도 가능하므로 먼저 범위를 확인한다.
if (index == values.size() || values[index] != target) return -1;
return static_cast<std::ptrdiff_t>(index);
}
int main() {
const std::vector<int> values{1, 3, 3, 7, 9};
std::cout << lowerBound(values, 3) << '\n';
std::cout << lowerBound(values, 6) << '\n';
std::cout << indexOfSorted(values, 6) << '\n';
return 0;
}1
3
-1TypeScript
배열 [1, 3, 3, 7, 9]에서 중복된 3과 배열에 없는 6을 차례로 찾아보자. 입력 배열은 오름차순으로 정렬된 유한한 수여야 한다. 호출할 때마다 정렬 여부를 검사하면 탐색 전에 스캔이 들어가 로그 시간 이점이 사라지므로, 정렬 상태는 호출자가 보장하는 전제 조건(가드 클로즈 참고)으로 둔다.
function lowerBound(values: readonly number[], target: number): number {
let lo = 0;
let hi = values.length;
// 불변식: values[0..lo) < target 이고 values[hi..n) >= target
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (values[mid]! < target) lo = mid + 1;
else hi = mid;
}
return lo;
}
function indexOfSorted(values: readonly number[], target: number): number {
const index = lowerBound(values, target);
// 삽입 경계 인덱스가 배열 범위 안이고 실제 값이 일치하는지 확인한다.
return index < values.length && values[index] === target ? index : -1;
}
const values = [1, 3, 3, 7, 9];
console.log(lowerBound(values, 3));
console.log(lowerBound(values, 6));
console.log(indexOfSorted(values, 6));1
3
-13이 처음 나오는 인덱스는 1이다. 6의 삽입 경계는 값 7이 자리한 인덱스 3이므로, 실제 일치 여부까지 확인하는 indexOfSorted는 -1을 돌려준다. 중간 인덱스는 비트 시프트(>> 1) 대신 Math.floor를 써서 JavaScript의 32비트 정수 절삭을 피했다.
비용과 실무 경계
배열 임의 접근과 크기 비교가 상수 시간일 때, 길이 인 배열에서 후보 위치 개를 절반씩 줄이므로 시간 복잡도는 , 추가 공간 복잡도는 이다.
실무에서는 세 가지 경계를 주의해야 한다. 첫째, 연결 리스트처럼 인덱스 임의 접근에 이 걸리는 구조에서는 중간 원소를 찾는 비용 때문에 이진 탐색의 이점이 사라진다. 둘째, 경계를 찾은 뒤 배열 중간에 실제로 원소를 끼워 넣거나 지우면 뒤쪽 원소를 밀고 당기는 데 시간이 든다. 삽입과 삭제가 잦다면 정렬 배열 대신 균형 이진 탐색 트리나 B-트리를 써야 한다. 셋째, 부동소수점 배열에 NaN이 섞이면 <와 >= 비교가 모두 거짓이 되어 전순서(total order) 전제가 깨지므로 탐색 전에 걸러내야 한다.
같이 보기
각주
- Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, §6.2.1 ("Searching an Ordered Table"), pp.409–426. ↩
- Jon Bentley, “Writing Correct Programs,” Communications of the ACM 26(12), 1983, pp.1040–1045. 원문, DOI. ↩
- Joshua Bloch, “Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken,” Google Research, 2006-06-02. 저자 글. ↩