Binary Search를 구현할 때 주의할 점
“Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…” — Donald Knuth.
“이진 검색의 기본 개념은 비교적 간단하지만 세부 사항은 놀랍도록 까다로울 수 있습니다.” — Donald Knuth.
Art of Computer Programming 3: 정렬과 검색 6.2.1에서는 이진 검색의 기본 개념은 비교적 간단하지만 세부 사항은 놀랄만큼 까다로울 수 있다는 것을 명시하고 있습니다.
실제로 대부분의 사람들이 작성하는 이진 검색 코드는 잠재적인 버그를 갖고 있다고 하며, 이 글은 해당 내용을 다루고 있습니다.
Binary search
Binary search는 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘입니다. 처음 중간의 값을 임의로 선택하고, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있습니다. 경계값 검사, 하한값과 상한값을 지정하는 방식, 재귀적 작동 방식의 여부 등 구현에 다소 차이가 존재할 수 있지만, 아래의 방식으로 구현한 이진 검색 코드는 이진 검색을 알고 있는 사람에게 익숙한 코드일 것입니다.
처음 선택한 중앙값(midVal)이
- 찾고 있는 값(key)보다 크면 그 값은 새로운 최댓값이 됩니다.
- 찾고 있는 값(key)보다 작으면 그 값은 새로운 최솟값이 됩니다.
// C or C++
int binarySearch(int a[], int key, int len) {
int low = 0, high = len - 1;
while (low <= high) {
int mid = (low + high) >> 1;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // find key
}
return -(low + 1);
}
이진 검색은 검색 원리상 정렬된 리스트에서만 사용할 수 있다는 단점이 있지만, 최악의 경우에도 시간복잡도 을 보장합니다.
Binary search 구현시 주의할 점
하지만 이러한 이진 검색 코드를 구현할 때는 주의할 점이 있습니다.
바로 위에서 보았던 코드를 보고 눈치채셨나요?
별 문제 없는 이진 검색 코드라고 생각되었다면 아래 문제를 풀어봅시다.
[LeetCode] 278. First Bad Version
(내용은 아래에서 계속됩니다.)
만약 위의 코드에서 검색하고자 하는 리스트의 인덱스 상한이 이상의 값이면 이진 검색 알고리즘이 의도한 대로 동작하지 않을 수 있습니다.
C++에서 int 배열을 크기로 동적으로 할당한 예시를 보겠습니다. (이때의 메모리 소비는 약 4GB입니다.)
배열 인덱스 범위의 하한과 상한이 [0, (Array length - 1)]이므로,
을 인덱스 범위로 포함시키기 위해 +1를 합니다.
1: const int MAX = (1 << 30) + 1; // (2^30) + 1 == 1,073,741,825
2:
3: int binarySearch(int a[], int key, int len) {
4: int low = 0, high = len - 1;
5: while (low <= high) {
6: int mid = (low + high) >> 1;
7: int midVal = a[mid];
8: if (midVal < key)
9: low = mid + 1;
10: else if (midVal > key)
11: high = mid - 1;
12: else
13: return mid; // find key
14: }
15: return -(low + 1);
16: }
17:
18: int main() {
19: int *A = new int[MAX];
20: for (int i = 0; i < MAX; ++i) {
21: A[i] = i + 1;
22: }
23: int pos = binarySearch(A, MAX, MAX);
24: cout << pos << "\n";
25: delete[] A;
26: return 0;
27: }
배열 크기 정의에 이용된 MAX 값은 1073741825이고, 찾는 값(key)이 MAX입니다. 따라서 함수 binarySearch의 예상 반환값 및 24번 라인의 최종 출력값은 인덱스 상한에 해당하는 1073741824(2^30)가 될 것으로 예상할 수 있습니다.
하지만 실제로는 6번 라인에 의해서 정수형 오버플로가 발생하고 음수 인덱스를 참조하게 되는 과정에서 허용되지 않은 메모리 영역 참조로 인해 segmentation fault가 발생하게 됩니다.
(Java의 경우에는 ArrayIndexOutOfBoundsException가 발생합니다.)
에러가 발생하는 이유를 좀 더 자세히 적어보자면,
배열 길이는 1,073,741,825이며 찾으려는 값은 a[1073741824]에 있습니다. 따라서 low가 high의 초기값인 len - 1(1,073,741,824)과 동일해지는 순간이 존재합니다. 이것은 어느 한 순간 low + high의 결과가 2,147,483,648이 된다는 것을 의미하는데, 이 값은 int의 상한값인 2,147,483,647()을 초과하므로 오버플로가 되면서
-2,147,483,648가 되고, 이 값을 2로 나누기 때문에 mid 값은 -1,073,741,824이 됩니다.
최종적으로 7번 라인에서 a[mid]는 a[-1073741824] 위치를 참조하려고 하면서 에러가 발생합니다.
이진 검색 알고리즘이 처음 고안되었을 시기에는 지금 처럼 개인 PC가 보급화 되지 않았을 뿐더러 가용 메모리도 적었습니다. 마찬가지로 알고리즘을 학습할 때 제한된 데이터 범위 또는 제한된 시스템 리소스(RAM 등) 환경 내에서 이루어지다보니 인덱스 경계를 깊게 고려하지 못하는 경우가 발생합니다.
그리고 지금은 올바로 수정되었지만 과거 Java JDK(java.util.Arrays)에서 제공하는 binarySearch메소드에서도 이와 동일한 문제가 9년 동안 존재했다고 하니, 이진 검색을 사용할 때 범위가 큰 경우에는 경계값을 주의 깊게 살펴야 합니다.
해결 방법
이진 검색 알고리즘에서 low, high, mid를 unsigned int 또는 더 큰 정수를 표현할 수 있는 자료형으로 바꾸어 오버플로 문제를 해결할 수도 있지만 아래 코드로 대체할 수도 있습니다.
6: int mid = low + ((high - low) >> 1);
6: int mid = ((unsigned int)low + (unsigned int)high) >> 1;
그리고 Java의 경우에는 unsigned right shift operator를 지원하는데, 이것은 부호 비트를 고려하지 않고 최상위 비트를 무조건 0으로 채우기 때문에 (low + high)의 결과를 우측으로 1비트 시프트 연산 하는 과정에서 오버플로가 발생하는 것을 방지할 수 있으며 다음과 같이 활용할 수 있습니다.
6: int mid = (low + high) >>> 1;
아래는 CPP에서 이진 검색 함수를 만들고 호출할 때 발생하는 사소한 실수입니다.
C++ std::vector 사용시 참조자를 이용하지 않음
참조자(&) 없는 매개변수는 복사를 수행합니다.
C++에서 제공하는 라이브러리인 std::vector를 사용하면서 이진 검색을 직접 함수형태로 구현할 때 매개변수를 다음과 같이 선언하는 경우가 있습니다.
int binarySearch(const vector<int> a, int key) {
int low = 0, high = (int)a.size() - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int midVal = a[mid];
if (midVal < key)
low = mid + 1;
else if (midVal > key)
high = mid - 1;
else
return mid; // find key
}
return -(low + 1);
}
int main() {
// ...
const int MAX = 50000000;
vector<int> v;
v.resize(MAX);
for (int i = 0; i < MAX; ++i) {
v[i] = i + 1;
}
int pos = binarySearch(v, MAX);
cout << pos << "\n";
return 0;
}
위 함수 구조에서 문제가 되는 부분은 함수 vector 타입의 매개변수에 참조자(&)를 사용하지 않았다는 것입니다.
따라서 main 함수의 v가 binarySearch 함수의 매개변수 a로 전달될 때 복사 생성자가 호출되고 binarySearch(v, MAX)가 호출될 때마다 v가 갖는 50,000,000개의 원소를 벡터 매개변수 a에 복사합니다. 이진 검색의 시간복잡도는 이지만 복사 연산의 시간
만큼 추가적으로 소요되고, 소비하는 메모리도 (main 함수에서의
v, binarySearch 함수에서의 a) 2배가 됩니다.
아래 코드와 같이 반복문 내부에 쿼리 형태로 binarySearch를 호출할 때, 함수 매개변수에 참조자가 없다면 v의 원소를 a에 복사하는 과정이 반복 1회 때마다 발생하게 되고 이것만 놓고 봤을 때에도 시간복잡도는 입니다.
(while : N, vector copy : N, binarySearch : log N)
int binarySearch(const vector<int> a, int key) {
...
}
int main() {
...
int pos, key;
while (true) {
std::cin >> key;
...
pos = binarySearch(v, key);
cout << pos << "\n";
...
}
return 0;
}
따라서 이러한 불필요한 복사를 방지하기 위해서는 참조자(&)를 사용하여 다음과 같이 코드를 작성해야 합니다.
int binarySearch(const vector<int>& a, int key) {
...
}
비슷한 사례
위 경우와 조금 비슷한 사례를 들어보자면, 문자열 길이를 구하기 위해 strlen함수를 반복문의 조건식에 사용하는 경우를 생각해볼 수 있습니다.
문자열의 길이만큼 반복한다는 것에만 중점을 둘 때 아래의 worst case와 같이 잘못된 코드를 작성하는 사례를 가끔씩 보게 됩니다.
(이 부분에 대해 컴파일러가 최적화를 수행하는 경우도 있다고 하지만 여기서는 고려하지 않겠습니다. 시간 복잡도와 연관짓기 위해 worst라는 용어를 사용하였습니다.)
실상 worst case 코드는 반복문을 한 번 수행할 때마다 문자열의 길이를 구하고 있는 것인데, 여기서 문자열 길이를 구하는 strlen의 시간 복잡도는 ,
for-loop의 시간 복잡도가 이므로 전체 시간복잡도는
입니다.
시간 복잡도 측면에서
strlen을 사용할 때는 문자열 길이를 변수에 미리 구하여 사용하는 것이 좀 더 낫다고 볼 수 있습니다.
std::string을 이용하는 경우에는 string 클래스에 정의된 멤버 함수를 사용할 수 있습니다.std::string은 문자열의 길이를 별도로 저장하는데, 멤버 함수인size()또는length()는 이미 계산된 문자열 길이만 곧바로 반환하는 형태이므로 시간 복잡도가O(1)입니다. (컴파일러가 수행해주는 최적화에 실제 수행 속도는 상이할 수 있습니다.)
char str[1024];
...
// C worst case
for (int i = 0; i < strlen(str); ++i) { // O(N^2)
...
}
// C best case
int len = strlen(str); // O(N)
for (int i = 0; i < len; ++i) {
...
}
std::string s;
...
for (int i = 0; i < (int)s.length(); ++i) { // OK
...
}
// 하지만 일반적으로 반복문을 수행하면서 결과가 변경되지 않으면
// 반복문의 조건 부분에서 함수 호출을 피하기 위해 아래처럼 사용하기도 합니다.
size_t len = s.length();
for (size_t i = 0; i < len; ++i) { // OK
...
}