C++ lower_bound, upper_bound 활용하기

1. 정리

c++에서는 이진 검색(Binary Search)를 함수로 제공하고 있습니다. 이상과 초과에 대한 기준으로 두 개를 제공하고 있는데 각각 lower_bound와 upper_bound 입니다. 데이터 양이 적을 경우에는 순차 검색(Sequential Search)과 비교 했을 때, 크게 의미가 없거나 오히려 안좋아질 수도 있지만, 데어터 양이 많을 경우에는 기하급수적으로 성능이 좋아집니다.

( 코딩 문제 사이트에서 순차 탐색을 이용했을 때, 런타임 에러가 발생했으나 이진 검색을 이용하여 풀어보면 해결되는 경우가 많네요. )

 

---

ko.wikipedia.org/wiki/%EC%88%9C%EC%B0%A8_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

순차 검색 알고리즘

ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

이진 검색 알고리즘

---

lower_bound와 upper_bound는 조건에 따라 그리고 기호에 따라 사용하시면 됩니다. 두 함수는 정렬이 되어 있는 경우에 활용할 수 있는데, 먼저 정렬된 vector<int>와 검색된 인덱스를 담을 변수를 선언해보죠. 아래 코드와 같이 0~5까지의 정수를 선언했습니다.

vector<int> v = { 0, 1, 2, 3, 4, 5 };
int index;

 

현재는, 벡터가 오름차순으로 되어 있습니다. 오름차순일 때, 검색값 1보다 이상이 되는 값을 만족하는 인덱스를 검색해보죠. lower_bound는 return 값이 iterator로 나오므로, int형으로 값을 취하고 싶을 때는 begin()이나 end()를 이용해야 합니다. 아래 코드에서는 검색된 인덱스 값에서 초기 위치를 빼주므로 검색된 인덱스 값이 나올 거에요.

출력

Index:1

//오름차순이고 검색값 이상으로 되는 값의 인덱스를 찾을 때,
index = lower_bound(v.begin(), v.end(), 1) - v.begin();
cout << "Index:" << index << endl << endl;

 

이번에는 오름차순일 때, 검색값보다 초과가 되는 값을 만족하는 인덱스를 검색해보죠. 방식은 동일하고 함수만 upper_bound로 바꾸시면 됩니다. 위의 경우와 달리, 인덱스가 2가 출력됩니다. 1보다 초과되는 값은 2이고 2값의 인덱스가 2이기 때문이에요.

출력

Index:2

//오름차순이고 검색값 초과로 되는 값의 인덱스를 찾을 때,
index = upper_bound(v.begin(), v.end(), 1) - v.begin();
cout << "Index:" << index << endl << endl;

 

지금까지는 오름차순일 때, 이진 검색하는 방법이었습니다. 그렇다면 내림차순으로 된 벡터의 이진 검색을 어떻게 해야 할까요? 한참을 고민했지만, 생각보다 답은 간단했습니다. 함수에서 파라미터 값을 변경해주면 되기 때문이죠. 

먼저, 벡터를 내림차순으로 재선언해주고 이진 검색을 해보겠습니다. 차이가 보이시나요? lower_bound 함수의 파라미터를 추가했습니다. 추가한 파라미터의 값은 greater<int>()입니다. 파라미터 하나로 이상을 검색하던 함수가 이하를 검색하는 함수로 변했네요.

출력

Index:4

//내림차순이고 검색값 이하로 되는 값의 인덱스를 찾을 때,
v = { 5, 4, 3, 2, 1, 0 };
index = lower_bound(v.begin(), v.end(), 1, greater<int>()) - v.begin();	
cout << "Index:" << index << endl << endl;

 

이번에는 내림차순에서 미만이 되는 값을 찾아보겠습니다. 방법은 지금까지와 유사합니다. upper_bound 함수와 greater<int>() 파라미터를 이용하시면 됩니다.

출력

Index:5

//내림차순이고 검색값 미만으로 되는 값의 인덱스를 찾을 때,
index = upper_bound(v.begin(), v.end(), 1, greater<int>()) - v.begin();
cout << "Index:" << index << endl << endl;

 

짧은 코드라인으로 좋은 성능의 검색 알고리즘이 만들어졌네요. 처음 접하면, 헷갈릴수도 있어 각각의 경우에 간략히 정리하면 아래와 같아요.

이상, 이하: lower_bound

초과, 미만: upper_bound

오름차순 파라미터: -

내림차순 파라미터: greater<int>

 

2. 전체코드

#include <bits/stdc++.h>

using namespace std;

int main() {
	vector<int> v = { 0, 1, 2, 3, 4, 5 };
	int index;

	//오름차순이고 검색값 이상으로 되는 값의 인덱스를 찾을 때,
	index = lower_bound(v.begin(), v.end(), 1) - v.begin();
	cout << "Index:" << index << endl << endl;

	//오름차순이고 검색값 초과로 되는 값의 인덱스를 찾을 때,
	index = upper_bound(v.begin(), v.end(), 1) - v.begin();
	cout << "Index:" << index << endl << endl;

	//내림차순이고 검색값 이하로 되는 값의 인덱스를 찾을 때,
	v = { 5, 4, 3, 2, 1, 0 };
	index = lower_bound(v.begin(), v.end(), 1, greater<int>()) - v.begin();	
	cout << "Index:" << index << endl << endl;

	//내림차순이고 검색값 미만으로 되는 값의 인덱스를 찾을 때,
	index = upper_bound(v.begin(), v.end(), 1, greater<int>()) - v.begin();
	cout << "Index:" << index << endl << endl;

	return 0;
}