이진 탐색, 이분 탐색(binary search) 구현시 고려할 것들

binary search 알고리즘은 번역해서 이진 탐색이라고도 부르고, 이분 탐색이라고도 부른다. 사실 컴퓨터공학을 전공하면, 자료구조 과목을 배울 때 배우는 탐색 알고리즘 중 하나로, 정말 유명하고 자료도 많은 알고리즘 중 하나이다.

 

학교 전공과목시간에 이진 탐색을 처음 배웠을때는 신기하긴 했지만 나중에 더욱 복잡하고 어렵고 멋져보이는 알고리즘들을 보면 이 이진 탐색은 결국 적당히 재귀로 구현해서 쓰기만 하면 되는 것 같은 별 것 아닌 알고리즘 같아 보인다.

 

하지만 이렇게 간단하고 비교적 쉬운 기초적인 알고리즘이지만, PS를 할 때 이 이진 탐색의 아이디어를 이용해서 최적화를 하거나, parametric search를 하거나 하는 활용도가 꽤 있는 편이며, 사용할 수 있는 정확한 상황을 판단하고 버그없이 구현하는 것이 생각보다는 어려울 수 있다.

 

이번 포스팅에서는 기본적인 이진 탐색의 개념에 대해서는 알고 있는 사람이 구현 시, 적용 시 유의해야 할 점들을 한번 씩 짚고 넘어가보도록 하자.

적용할 수 있는 경우

이진 탐색 알고리즘은 항상 적용할 수 있는 것은 아니다. 몇 가지 조건이 필요하다.

1. 원소가 정렬이 되어 있을 것(오름차순이든 내림차순이든)
2. 원소의 Random Access가 가능해야 한다.

원소가 정렬이 되어 있어야지 중간에 한 곳을 딱 집어서, 결과를 본 뒤 그 지점의 이전과 이후의 값을 예측을 할 수 있다. 오름차순이든 내림차순이든 정렬이 되어 있어야 한다. 그리고 만약, 중복되는 원소가 있다면, 일반적인 binary search가 아닌, upper_bound와 lower_bound를 각각 구한 뒤, lower_bound부터 upper_bound직전까지 다 훑으면, 해당 크기의 모든 원소를 확인할 수 있다. 원소가 중복이 있는지 아닌지도 구현시 디테일을 바꾸게 하는 하나의 체크 포인트이다.

 

그리고 binary_search 자체가 아닌 다른 알고리즘에 녹아들어가거나, parametric search인 경우 정렬은 아니지만, 중간 임의의 값을 look up 했을 때 그 이전과 이후의 값에 대한 예측이 가능한 경우도 정렬이 되어 있는 것과 마찬가지로 볼 수 있다.

 

원소의 Random Access가 가능하다는 것은, C언어의 배열 처럼, index만 알면 특정 arr[index] 값을 $O(1)$의 시간복잡도로 참조가 가능하냐는 것이다. 사실 Random Access가 불가능하더라도 이분탐색은 가능하긴 하지만, $O(1)$의 시간복잡도로 Random access가 불가능하다면 이분탐색으로 $O(lgN)$의 성능 향상은 기대하기 힘들다. Random access가 불가능하고 sequential access만 가능한 Linked list에서 이분 탐색을 하지 않는 이유도 이러한 이유이다.

 

구현시 체크할 점

이분 탐색은 크게 두가지 구현방법이 있는데, 재귀(recursion)와 반복(iteration)이다. 그런데 함수 프롤로그와 에필로그의 오버헤드를 줄일 수 있는 반복(iteration)방식으로 구현하는 것이 성능이 일반적으로 더 좋고, 간편하다.

while문을 이용해서 쉽게 구현할 수 있는데, 이때 디테일을 잘못 구현하게 되면 특정 상황에서 무한루프가 돌면서 이분 탐색이 종료하지 않을 수 있다.

잘 구현된 경우

사실 이제부터 이야기하는 코드들은 이진탐색이라기 보다는 parametric search에 가깝다. ok 함수를 만족하는 정수 값 중 가장 끄트머리에 있는 값을 찾는다고 보면 된다. -INF~10까지의 값은 ok 함수에서 true를 리턴하고 11~INF의 값은 false를 리턴한다고 하면 10을 찾는 것이다.

int left, right; // [left, right) range
while (left + 1 < right) {
	int mid = (left + right) / 2;
	if (ok(mid)) {
		left = mid;
	} else {
		right = mid;
	}
}
//return left
C++

위와 같은 방식으로 코드를 짤 수 있다.

left, right는 범위를 반 개구간으로 해서 [left, right)라고 표현을 했는데, 원하는 값은 left보다는 크거나 같고, right보다는 작은 범위 안에 있다는 뜻이다. 중고등학교 수학시간에 아마 배웠겠지만 [와 ]는 inclusive로 이상, 이하에 해당하고 (와 )는 exclusive로 초과, 미만에 해당한다.

 

그러면 만약 범위가 [2, 3) 처럼 된다면, 해당 범위를 만족하는 정수는 2밖에 없게 된다. 따라서 탐색을 계속 지속하려면 right가 left보다 2이상 커야 한다. 따라서 while문의 진행 조건도 left + 1 < right와 같이 된다.

 

그리고 중간값인 mid를 구해서, mid가 range안에 포함이 된다고 하면 ok함수가 true를 리턴하게 되고 이때, left값을 mid로 바꾼다. left가 찾는 값이 될 수도 있으므로 inclusive인 left로 들어가도 무방하다.

 

mid가 range안에 포함이 되지 않는다면 ok함수가 false를 리턴하게 되고, right를 mid로 바꾼다. right 값은 exclusive이므로 찾는 값이 포함되지 않는다는 뜻이 된다.

 

그렇다면 이 while문이 무한루프를 돌 수 있을까? while문이 무한루프를 돌려면, loop을 한번 돌 때, 범위가 하나도 줄어들지 않는 경우가 생겨야 한다.

 

mid를 계산하는 것과, ok 함수의 리턴값에 따른 left, right값의 update 시 줄어들지 않는 경우가 있는지를 한번 확인해보자. 

사실 범위가 클 때에는 잘 줄어든다. 그리고 탐색이 거의 다 되어서 범위가 매우 줄어들었을 때, off by one error로 값이 줄어들지 않는 경우가 있을 수 있는데 홀수 짝수를 예시로 몇가지 값을 넣어보면 바로 알 수 있다.

 

[2, 3)이면 종료조건이 되므로 [2, 4)와 [3, 5)를 예시를 들어보자.

[2,4)인 경우 mid=3이 되며, 결과가 어떻든 [3,4)이거나 [2,3)으로 종료가 된다.

[3,5)인 경우 mid=4가 되며, 각각 [4,5)이거나 [3,4)로 종료가 된다.

 

이 경우는 무한루프가 돌지 않는 코드가 되게 된다.

 

그리고 최종적으로 리턴하는 값 자체도 inclusive인 left의 값을 리턴하면 우리가 찾는 값이 된다.

 

잘못 구현될 수 있는 경우

사실 위에서 예시로 든 경우는 C++ STL container들이 흔히 쓰는 방식인 [start, end)의 반개구간으로 하는 식이라서 간단하면서도 에러가 잘 없는 코드 패턴이 나왔다. 하지만 [start, end]와 같은 폐구간으로 설정을 하는 경우 조금 다를 수 있겠다.

비슷하게 아래와 같이 코드를 짜 보았다고 생각해보자.

int left, right; // [left, right] range
while (left < right) {
	int mid = (left + right) / 2;
	if (ok(mid)) left = mid;
	else right = mid;
}
// return left;
C++

완전 폐구간이므로, left == right가 되어야지 하나의 범위로 줄어든다. 따라서 while문의 조건이 left < right로 바뀌었다.

하지만 위의 코드는 잘못 짠 코드이다. 무엇이 잘못되었을까?

 

일단 값을 잘못 찾을 수 있으며, 무한루프 역시 돌 수 있다.

 

무엇이 잘못되었고, 어떻게 고쳐야 할 지 한번 고민을 해 보고 아래의 올바른 코드를 한번 확인해보도록 하자.

 

정정된 올바른 코드

int left, right; // [left, right] range
while (left < right) {
	int mid = (left + right + 1) / 2;
	if (ok(mid)) left = mid;
	else right = mid - 1;
}
// return left;
C++

일단 ok(mid)가 return false를 한 경우 mid는 범위안에 들어오지 않는다. 근데 right를 mid로 하면 inclusive이므로 mid가 범위에 들어온다는 오류를 범하게 된다. 따라서 mid - 1를 적용해야 한다.

그리고 이런 경우, 무한루프가 돌 수 있는데 범위가 [2, 3]이라고 가정해보자.

그리고 정말 찾는 값은 3이라고 생각해보자. 1~3의 값은 모두 ok함수에서 true를 리턴하고,

4이상의 값은 false를 리턴한다.

이때, mid=(2+3)/2 = 2가 되고, ok(2)=true가 되는데, left=mid=2로 범위가 그대로가 된다.

이 경우 [2,3]라는 범위에서 [3,3]라는 범위로 줄어들지 못하고 평생 저렇게 남게 된다. 즉 무한루프다.

이런경우 결국 left값이 범위를 줄여줘야 하는데, mid계산 시 2로 나누면서 LSB가 날라가게 되므로 나누기 전에 1을 더해서 floor((left+right)/2)가 아닌 ceil((left+right)/2)를 구하도록 해주면 정확하게 구현이 된다. 그리고 left를 리턴하면 된다.

생각나는대로 글을 쓰다 보니 글에 오류나 이해가 가지 않는 부분이 있을 수 있는데, 댓글로 피드백을 준다면 정정하도록 하겠습니다.