C++ - Algorithm 헤더 파일 binary_search(), lower_bound(), upper_bound()

이번에는 모든 분들이 다 아시는 sort를 제외한 다른 sorting 함수와 lower(OR upper)_bound()를 알아보도록 하겠습니다.

 

[binary_search(arr_begin,arr_end,find_value) : 검색해주는 함수로서 찾는 값이 존재하면 True, 아니면 False를 리턴한다.]

 

이진 탐색(binary search)를 사용하는데, 정렬이 되어 있다는 가정하에 값을 빨리 찾고 싶을 때 사용합니다.

arr_begin - 시작

arr_end - 끝

find_value - 찾고자 하는 값

 

[1 4 5 7 8 11 12 12 16 21 35]

11개의 값이 있다고 가정하자, 만약 여기서 21이라는 값을 찾고 싶다면, 어떻게 할까? 

반복문을 사용해서 처음부터 끝까지 비교를 해 보면 됩니다. 하지만 이러면 적어도 10번은 비교를 해야 값을 찾을 수 있죠.

물론 끝에서부터 하면 2번만이지만, 그럴 때는 값 "4"를 찾을 때는 오히려 느려집니다.

값이 없을 때는, 11개의 값을 다 비교해 봐야 하는 것이고요.

 

이것보다 빠르게 값의 유무를 판단하는 방법 중 하나가 이진 탐색입니다.

 

이진탐색이란 : 이진 탐색은 일단 제일 가운데에 있는 값을 하나 뽑습니다. 그리고 값들이 정렬되어 있다는 점을 이용해서, 관찰할 영역을 점점 좁혀 나갑니다.

 

[1 4 5 7 8 11 12 12 16 21 35] : 

21은 11보다 크니까, 11보다는 오른쪽에 있을 것입니다. 이제 11의 오른쪽 영역에서 다시 21을 찾아보면 됩니다.

 

[1 4 5 7 8 11 12 12 16 21 35] :

오른쪽 영역에서 가운데 값은 16입니다. 16보다 21이 크니까, 다시 16의 오른쪽 영역을 찾아가면 되는 겁니다.

 

[1 4 5 7 8 11 12 12 16 21 35] :

21, 35 영역에서 제일 가운데 값이란 것은 없지만, 이럴 때는 제일 가운데의 2개 값 중 하나를 고르는 방식을 사용하면 됩니다. 보통 왼쪽 값을 고르게 됩니다. 그런데, 고른 중간값이 21이죠. 이러면 값을 찾은 겁니다.

 

 

9를 찾는다고 해 봅시다.

[1 4 5 7 8 11 12 12 16 21 35] :

일단, 중간값 11보다는 9가 작으므로 왼쪽 영역을 봅니다.

 

[1 4 5 7 8 11 12 12 16 21 35] :

중간값 5보다는 9가 크므로, 오른쪽을 봅니다.

 

[1 4 5 7 8 11 12 12 16 21 35] :

그 다음 영역의 중간값 7보다는 9가 크므로, 또 오른쪽을 봅니다.

 

[1 4 5 7 8 11 12 12 16 21 35] :

그런데 그 한 개의 값이 자동적으로 중간값이 되고, 그건 9가 아니네요.

이러면 값을 찾지 못한 채로 끝나고, 9가 없다고 판정하게 됩니다.

 

값이 1000개라고 할 때, 많아봐야 단 10번의 비교만 필요한 셈이므로 1000번의 비교와는 도저히 비교조차 불가능할 정도로 빨라지게 됩니다. 이를 시간복잡도(time complexity)라는 개념으로 표현할 수 있는데, 자료구조나 알고리즘에서 더 자세히 배울 수 있으므로 일단 그런 게 있다 정도만 하겠습니다.

 

이걸 구현해 놓은 것이 binary_search() 함수입니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(){

	int a[10] = {17, 25, 67, 84, 90, 30, 55, 6, 9, 28};
	sort(a, a + 10);

	cout << "값 55: ";
	if(binary_search(a, a+10, 55)) cout << "찾았습니다." << endl;
	else cout << "찾지 못했습니다." << endl;

	cout << "값 80: ";
	if(binary_search(a, a+10, 80)) cout << "찾았습니다." << endl;
	else cout << "찾지 못했습니다." << endl;

	return 0;
}

배열에서 55, 80을 각각 찾아본 결과입니다. 먼저 배열을 정렬해야 한다는 점을 까먹지 마세요!

값 55: 찾았습니다.
값 80: 찾지 못했습니다.

이것들은 기본적으로 이진 탐색을 하는데, 주어진 값을 기준으로 하여 찾아냅니다. (때문에 역시 데이터가 정렬되어 있어야 사용할 수 있습니다.)

lower_bound() 함수는 주어진 값보다 크거나 같으면서 제일 작은 값을 찾고,

upper_bound() 함수는 주어진 값보다 크면서 제일 작은 값을 찾습니다.

두 함수의 차이는, 같은 값을 포함하느냐 아니냐입니다. 그런 값이 없으면 구간의 끝 주소나 이터레이터를 반환하게 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(){

	int a[10] = {17, 25, 67, 84, 90, 30, 55, 6, 9, 28};
	sort(a, a+10);

	cout << "lower bound 55: " << *lower_bound(a, a+10, 55) << endl;
	cout << "upper bound 55: " << *upper_bound(a, a+10, 55) << endl;

	cout << "lower bound 80: " << *lower_bound(a, a+10, 80) << endl;
	cout << "upper bound 80: " << *upper_bound(a, a+10, 80) << endl;

	return 0;
}

지금은 배열에서 사용하고 있으므로, 주소를 반환하게 됩니다. 단순히 * 연산자를 사용해서 가리키는 값을 알 수 있습니다.

lower bound 55: 55
upper bound 55: 67
lower bound 80: 84
upper bound 80: 84

결과를 보면 차이를 확실히 알 수 있습니다.

lower_bound() 함수는 55도 포함하지만, upper_bound() 함수는 55는 포함시키지 않습니다.

80을 찾았을 때는 애당초 그런 값이 없으므로 결과는 동일하게 됩니다.

#include <iostream>
#include <algorithm>
using namespace std;

int main(){

	int a[10] = {17, 25, 67, 84, 90, 30, 55, 6, 9, 28}, *p;
	sort(a, a+10);

	p = lower_bound(a, a+10, 80);
	cout << "lower bound 80: ";
	if(p != a+10) cout << "a[" << p-a << "] = " << *p << endl;
	else cout << "NOT FOUND" << endl;

	p = lower_bound(a, a+10, 120);
	cout << "lower bound 120: ";
	if(p != a+10) cout << "a[" << p-a << "] = " << *p << endl;
	else cout << "NOT FOUND" << endl;

	return 0;
}

사실, 더 정확하고 자세한 사용법은 이러할 것입니다.

왜냐면 찾는 값이 없을 수도 있거든요. 그때는 배열의 끝 주소를 가리키게 될 텐데 거기다 무작정 * 연산자 붙여서 참조하려 들면 엄청난 일이 벌어질 테니... 먼저 리턴값이 영역의 끝인지 검사한 후 참조하는 것이 좋겠죠. 이때 리턴된 값과 시작 주소를 빼서 인덱스도 알아낼 수 있습니다.

lower bound 80: a[8] = 84
lower bound 120: NOT FOUND

벡터의 경우도 마찬가지로 사용하시면 됩니다. begin(), end() 함수를 잘 사용해서...

 

사실 이 함수들은, 애초부터 값이 항상 정렬되어서 저장되는 STL인 set과 매우 잘 맞습니다.

실제로 binary_search() 함수는 set에서 기본적인 함수 find(), count() 함수와 매우 유사하고, 뒤쪽 두 함수는 아예 전용 함수로 이름까지 똑같은 형태로 존재합니다.

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int main(){

	set<int> s;
	s.insert(17);
	s.insert(25);
	s.insert(67);
	s.insert(84);
	s.insert(90);
	s.insert(30);
	s.insert(55);
	s.insert(6);
	s.insert(9);
	s.insert(28);

	set<int>::iterator setIter;

	setIter = lower_bound(s.begin(), s.end(), 90);
	cout << "lower bound 90: ";
	if(setIter != s.end()) cout << *setIter << endl;
	else cout << "NOT FOUND" << endl;

	setIter = upper_bound(s.begin(), s.end(), 90);
	cout << "upper bound 90: ";
	if(setIter != s.end()) cout << *setIter << endl;
	else cout << "NOT FOUND" << endl;

	return 0;
}

일단 set을 사용하더라도, 기본적으로 이런 사용법이 가능하지만...

	setIter = s.lower_bound(90);
	cout << "lower bound 90: ";
	if(setIter != s.end()) cout << *setIter << endl;
	else cout << "NOT FOUND" << endl;

	setIter = s.upper_bound(90);
	cout << "upper bound 90: ";
	if(setIter != s.end()) cout << *setIter << endl;
	else cout << "NOT FOUND" << endl;

이렇게 바꿔 써도 같은 뜻이 됩니다! 물론, 이때는 무조건 set의 시작과 끝으로 범위가 고정되지만, 애초에 그렇지 않은 범위로 사용할 때가 더 흔치 않습니다.

lower bound 90: 90
upper bound 90: NOT FOUND

 

출처: https://m.blog.naver.com/PostList.nhn?blogId=kks227&categoryNo=163&logCode=0