이진 탐색(binary search) 알고리즘이 선형 탐색(linear search)보다 뛰어나다는 것은 잘 알려진 사실입니다. O(log n)의 시간 복잡도 덕분에 방대한 데이터 속에서도 빠르게 원소를 찾아낼 수 있죠. 그런데 의외로 실무에서 작성되는 많은 이진 탐색 코드에는 치명적인 결함이 숨어 있습니다.
문제가 있는 이진 탐색 구현
int binarySearch(int array[], int start, int end, int key){
if(start <= end){
int mid = (start + end) / 2; // 리스트의 중간 위치
if(array[mid] == key)
return mid;
if(array[mid] > key)
return binarySearch(array, start, mid-1, key);
return binarySearch(array, mid+1, end, key);
}
return -1;
}
위 코드는 start와 end 값이 작을 때는 완벽하게 동작합니다. 하지만 배열의 크기가 충분히 커져서 두 값의 합이 부호 있는 32비트 정수(int)가 표현할 수 있는 최댓값인 231 − 1을 초과하는 순간 이야기가 달라집니다. 바로 정수 오버플로우(integer overflow)가 발생하여 계산 결과가 음수로 되돌아가는(wrap around) 현상이 일어나기 때문입니다. 배열 인덱스로 음수를 사용할 수 없기 때문에, 이로 인해 잘못된 메모리 접근이나 프로그램 비정상 종료와 같은 심각한 문제가 발생할 수 있습니다.
참고로 이 버그는 2006년 당시 구글의 조슈아 블로흐(Joshua Bloch)가 표준 라이브러리의 이진 탐색 코드에서조차 이 결함이 발견되었다고 공개적으로 지적하면서 널리 알려지게 되었습니다. 그렇다면 이 문제를 어떻게 해결할 수 있을까요?
해결 방법 1: 거리 기반 중앙값 계산
int mid = start + ((end - start) / 2);
두 값의 합을 구하는 대신 start로부터의 상대적인 거리를 이용해 중간 위치를 계산하는 방식입니다. 두 값의 합 자체가 크게 계산되지 않으므로 오버플로우가 발생하지 않으며, 특정 언어에 종속되지 않고 어디서든 안전하게 사용할 수 있는 가장 보편적인 해결책입니다.
해결 방법 2: 부호 없는 우측 시프트 연산 (Java 전용)
int mid = (start + end) >>> 1;
자바의 >>> 연산자는 부호 비트를 확장하지 않고 오른쪽으로 시프트를 수행하기 때문에, 합계가 오버플로우되더라도 올바른 중앙값을 얻을 수 있습니다. 다만 C나 C++에는 이 연산자가 존재하지 않으므로 자바 환경에서만 사용할 수 있습니다.
해결 방법 3: 부호 없는 정수로 캐스팅 (C/C++)
int mid = ((unsigned int) low + (unsigned int) high) >> 1;
C나 C++ 환경이라면 두 변수를 unsigned int로 명시적으로 캐스팅한 뒤 시프트 연산을 수행하는 방식으로 동일한 효과를 얻을 수 있습니다.
겉보기에는 사소해 보이는 이 한 줄의 차이가 대규모 시스템에서는 치명적인 장애로 이어질 수 있습니다. 이진 탐색을 직접 구현할 때는 반드시 중앙값 계산 과정에서의 오버플로우 가능성을 점검하는 습관을 들이는 것이 좋습니다.