[C++ STL] lower_bound, upper_bound 요약 설명 (실전 알고리즘)

• 설명
• 사용법

   

   설명

 

 

lower_bound, upper_bound 둘 다 algorithm 헤더 안에 있는 함수이며 set같은 특정 컨테이너 안에도 메서드로 존재합니다,둘 다 이분탐색으로 구현되어있습니다.

 

lower_bound는 찾고자 하는 값보다 크거나 같은 값 중 가장 처음 나오는 값의 반복자를 반환합니다.

upper_bound는 찾고자 하는 값보다 큰 값 중 처음 나오는 값을 반환합니다.

lower_bound는 upper_bound에서 찾고자 하는 값과 같은 경우가 더해진 것 입니다.

 

 

주어진 데이터에서 찾고자 하는 값이 없는 경우에는 다음과 같습니다.

 

 

찾는 값이 주어진 데이터들 보다 크다면 

lower_bound는 end() 반복자를 반환합니다.

upper_bound 또한 end() 반복자를 반환합니다.

 

 

찾는 값이 주어진 데이터들 보다 작다면

lower_bound는 begin() 반복자를 반환합니다.

upper_bound 또한 begin() 반복자를 반환합니다.

 

(upper_bound는 찾는 값보다 큰 값을 찾기에 당연한 결과이고,

lower_bound도 같은 값이 없으면 큰 값을 찾기에 당연한 결과입니다.)

 

 

반복자를 배열의 인덱스처럼 표현하였습니다. 혼동주의

 

   사용법

 

1.

기본적인 사용법

 

/*   lower_bound(start, end, target)    */

#include <algorithm>


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

lower_bound(v.begin(), v.end(), 3);

int arr[5] = { 1, 2, 3, 4, 5 };

lower_bound(arr, arr+5, 3);

 

 

 

2.

인덱스 유도

 

반복자를 반환하기에 찾아낸 반복자에 시작반복자(begin())을 빼줌으로써

해당 반복자의 인덱스를 찾을 수 있습니다.

 

int idx = lower_bound(v.begin(), v.end(), 3) - v.begin();

 

 

 

3.

비교 매개변수 사용

 

이 두 함수에는 매개변수로 비교인자도 넣을 수 있는데 defualt로는 lower<>()이며 (오름차순)

다음과 같이 greater<>()를 붙여 사용할 수도 있다.

 

lower_bound(start, end, target, greater<>())

내림차순 정렬로 target보다 이하인 것 중 최대인 반복자를 반환해준다.

 

upper_bound(start, end, target, greater<>())

내림차순 정렬로 target보다 미만인 것 중 최대인 반복자를 반환해준다.

 

 

 

 

 

읽어주셔서 감사합니다. 부족한 부분이나 틀린 부분이 있다면 부디 알려주시면 감사하겠습니다.