[알고리즘/c++] lower_bound, upper_bound 활용

[참고]

https://en.cppreference.com/w/cpp/algorithm/lower_bound

std::lower_bound - cppreference.com

 

lower_bound

• key 값 보다 같거나 큰 원소를 찾는데 사용되는 알고리즘
• 찾지 못했을 경우 last 원소를 return 한다

upper_bound

• key 값을 초과하는 원소를 찾는데 사용되는 알고리즘
• 찾지 못했을 경우 last 원소를 return 한다

다만 자료구조가 정렬되어있는 상태여야 한다.

정렬되어있지 않을 경우 2진탐색을 하며 조건에 맞는 값을 찾으려 하기 때문에

원했던 값이 나오지 않을 수 있으니 주의하자

 

사용 방식은 lower_bound 랑 upper_bound 가 비슷하니 upper_bound 예시만 들어보겠다.

 

[코드] 사용 예시 

ex) array

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

/*
2023.01.01
순두부찌개
*/
int main()
{
	array<int, 5> arr { 1,2,3,4,5 };
	auto findReturn = lower_bound(arr.cbegin(), arr.cend(), 3);
	//array<int, 5>::const_iterator findReturn = std::lower_bound(arr.cbegin(), arr.cend(), 3);
	auto failReturn = lower_bound(arr.cbegin(), arr.cend(), 10);

	// !!! 찾는데 실패할 경우 return arr.end() 를 해주니 체크 필수 !!!!
	if (findReturn != arr.cend())
	{
		cout << *(findReturn) << endl;
		// 찾은 값 출력 : 3
		cout << findReturn - arr.cbegin() << endl;
		// 찾은 위치 출력 : 2 
	}
	else
	{
		cout << "find failed" << endl;
	}

	// 찾는데 실패하였다
	if (failReturn != arr.cend())
	{
		cout << *(failReturn) << endl;
		cout << failReturn - arr.cbegin() << endl;
	}
	else
	{
		cout << "find failed" << endl;
		// 이 부분으로 넘어온다
	}

}

 

ex) vector

array 랑 거의 똑같다

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

/*
2023.01.01
순두부찌개
*/
int main()
{
	vector<int> testVector { 1,2,3,4,5 };
	auto findReturn = lower_bound(testVector.cbegin(), testVector.cend(), 3);
	//vector<int>::const_iterator findReturn = std::lower_bound(testVector.cbegin(), testVector.cend(), 3);
	auto failReturn = lower_bound(testVector.cbegin(), testVector.cend(), 10);

	// !!! 찾는데 실패할 경우 return arr.end() 를 해주니 체크 필수 !!!!
	if (findReturn != testVector.cend())
	{
		cout << *(findReturn) << endl;
		// 찾은 값 출력 : 3
		cout << findReturn - testVector.cbegin() << endl;
		// 찾은 위치 출력 : 2 
	}
	else
	{
		cout << "find failed" << endl;
	}

	// 찾는데 실패하였다
	if (failReturn != testVector.cend())
	{
		cout << *(failReturn) << endl;
		cout << failReturn - testVector.cbegin() << endl;
	}
	else
	{
		cout << "find failed" << endl;
		// 이 부분으로 넘어온다
	}

	cout << "end" << endl;

}

 

ex) 원소가 사용자 지정 struct 인 경우

이 경우 lower_bound 4번째 인자에 람다를 이용하여 비교식을 넣어준다

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

/*
2023.01.01
순두부찌개
*/

struct UserInfo
{
	UserInfo(int level, int64_t exp) : Level(level), Exp(exp) {}
	int Level{ 0 };
	int64_t Exp{ 0 };
};

int main()
{
	vector<UserInfo> testVector;

	testVector.push_back(UserInfo(1,1));
	testVector.push_back(UserInfo(2, 1));
	testVector.push_back(UserInfo(3, 1));
	testVector.push_back(UserInfo(3, 10));
	testVector.push_back(UserInfo(4, 1));
	testVector.push_back(UserInfo(5, 10));

	// findUserInfo 의 Level, Exp 를 비교하여 같거나 큰 값을 찾아보자
	const UserInfo findUserInfo( 3, 5 );
	auto findReturn = lower_bound(testVector.cbegin(), testVector.cend(), findUserInfo,
		[](const auto& lhs, const auto& rhs)
		{
			if (lhs.Level < rhs.Level)
			{
				return true;
			}
			else if (lhs.Level == rhs.Level)
			{
				if (lhs.Exp < rhs.Exp)
				{
					return true;
				}
				return false;
			}
			return false;
		});
	
	// findReturn 결과값 : UserInfo(3, 10)
}

UserInfo Level 3보다 같거나 크고, Exp 5보다 같거나 큰 값을 탐색한 결과

결과 값 UserInfo(3, 10) 을 return 해준다.

이 때 만약 testVector 안에 UserInfo(3, 5) 가 있었다면 UserInfo(3,5) 을 return 해줬을 것 이다.

 

 

ex) 같거나 작은 원소 찾기

오름차순으로 정렬된 자료구조에 lower_bound 함수를 사용한다면 '같거나 큰 원소' 를 찾게 되지만

내림차순으로 정렬 후, 비교함수를 사용하면  '같거나 작은 원소' 도 찾을 수 있다.

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

/*
2023.01.01
순두부찌개
*/
int main()
{
	vector<int> v{ 1,2,3,4,5 };

	// 일단 내림 차순으로 정렬
	sort(v.rbegin(), v.rend());

	auto findReturn = lower_bound(v.cbegin(), v.cend(), 3,
		[](auto lhs, auto rhs)
		{
			return (lhs > rhs);
		});
	// findReturn 결과값: 3
}

만약 v 에 { 1,2,4,5,6} 이렇게 있었다면 3보다 같거나 작은 원소 결과값 2를 return 했을 것이다.