[C++] STL lower_bound, upper_bound 사용법

 

 

#include<algorithm> 헤더

lower_bound(arr, arr+N, value)

배열에서 범위 내의 원소들 중 value값 보다 크거나 같은 첫 번째 원소의 주소를 리턴합니다.
만약 그러한 원소가 없다면 end값을 리턴합니다.

 

upper_bound(arr, arr+N, value)

배열에서 처음으로 value값을 초과하는 원소의 주소를 반환합니다.
만약 그러한 원소가 없다면 end값을 리턴합니다.

 

 

 

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())을 빼줌으로써

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

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

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

// index = 1

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

// index = 2

 

 

 

3.

비교 매개변수 사용

 

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

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

 

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

// index = 4

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

// index = 5

 

10816.cpp 참고