[C++ STL] upper_bound, lower_bound, equal_range, binary_search

binary_search

• 정렬된 상태에서 사용해야 한다.
• 기본적으로 시작 Iterator, 끝 Iterator, value를 파라미터로 한다.
• bool 값을 리턴한다.
• 원하는 정렬 기준을 사용하려면 비교 함수를 파라미터로 넘기면 된다.

예시

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

cout<< binary_search(v.begin(),v.end(),3); // 1
cout<< binary_search(v.begin(),v.end(),7); // 0

upper_bound, lower_bound

• 이진 탐색으로 정렬된 상태에서 사용해야 한다.
• Iterator를 리턴한다.
• 원하는 정렬 기준을 사용하려면 비교 함수를 파라미터로 넘기면 된다.

예시

vector<int> v{ 10,20,30,30,20,10,10,20 }; 
sort(v.begin(), v.end()); // 10 10 10 20 20 20 30 30

vector<int>::iterator low, up;

low = lower_bound(v.begin(), v.end(), 20); // 찾는 값과 일치하면 해당 반복자 리턴
up = upper_bound(v.begin(), v.end(), 20); // 찾는 값을 초과하는 값 중 가장 작은 반복자를 리턴

cout << "lower_bound at position " << (low - v.begin()) << '\n'; // lower_bound at position 3
cout << "upper_bound at position " << (up - v.begin()) << '\n'; // upper_bound at position 6

equal_range

• lower_bound 와 upper_bound 를 같이 묶어 pair로 리턴한다.
• pair의 first는 lower, second는 upper 이다.
• 원하는 정렬 기준을 사용하려면 비교 함수를 파라미터로 넘기면 된다.

예시

vector<int> v{ 10,20,30,30,20,10,10,20 }; 
sort(v.begin(), v.end()); // 10 10 10 20 20 20 30 30
pair<vector<int>::iterator,vector<int>::iterator> bounds;

bounds = std::equal_range (v.begin(), v.end(), 20);

cout << "lower_bound at position " << (bounds.first - v.begin()) << '\n'; // lower_bound at position 3
cout << "upper_bound at position " << (bounds.second - v.begin()) << '\n'; // upper_bound at position 6