[알고리즘] STL lower_bound(), upper_bound(), equal_range()

lower_bound(), upper_bound(), equal_range()

lower_bound(), upper_bound(), equal_range()은 
이분 탐색을 통해서 어떤 값의 시작위치, 끝위치 또는 두 값모두를 리턴하는 함수이다.

ex) 1 1 2 3 4 4 4 5 6 7 8
lower_bound의 경우 인덱스 4(value : 4)
upper_bound의 경우 인덱스 7(value: 5)
equal_range의 경우 인덱스 4와 7(value: 4,5)

+ 참고 +
equal_range의 경우 distance() 함수와 같이 사용하면 좋다.

lower_bound()

vector<int>::iterator iter;
iter = lower_bound(s.begin(), s.end(), 4);
cout << "lower_bound 4: ";
if(iter != s.end()) 
    cout << *iter << endl;
else 
    cout << "no element" << endl;

upper_bound()

vector<int>::iterator iter;
iter = upper_bound(s.begin(), s.end(), 4);
cout << "upper_bound 4: ";
if(iter != s.end()) 
    cout << *iter << endl;
else 
    cout << "no element" << endl;

equal_range()

vector<int>::iterator iter;
iter = equal_range(b.begin(), b.end(), 4); 
cout << "lower_bound 4: ";
if(*iter2.first != s.end()) 
    cout << *iter2.first << endl;
else 
    cout << "no element" << endl;
cout << "upper_bound 4: ";
if(*iter.second != s.end()) 
    cout << *iter.second << endl;
else 
    cout << "no element" << endl;
int d = distance(*iter2.first, *iter2.second);
printf("%d",d);    // 4가 총 4개 있으므로 4가 출력된다.