Funkcje lower_bound oraz upper_bound są standardowymi szablonami funkcji biblioteki „algorithm”. Są to algorytmy niezmieniające dla danych posortowanych.

#include <algorithm>

wersja wykorzystująca „operator<”

	template <class ForwardIterator, class LessThanComparable>
 	ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
 				    const LessThanComparable& value);

wersja wykorzystująca predykat do spełnienia

        template <class ForwardIterator, class T, class StrictWeakOrdering>
 	ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,
 				    const T& value, StrictWeakOrdering comp);

wersja wykorzystująca „operator<”

	template <class ForwardIterator, class LessThanComparable>
 	ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
 				    const LessThanComparable& value);

wersja wykorzystująca predykat do spełnienia

        template <class ForwardIterator, class T, class StrictWeakOrdering>
 	ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last,
 				    const T& value, StrictWeakOrdering comp);

ForwardIterator first - element kolekcji, od którego rozpocznie się wyszukiwanie

ForwardIterator last - element kolekcji, który jako pierwszy nie będzie branu pod uwagę przez algorytm

const LessThanComparable& value - element wyszukiwany (do wstawienia)

StrictWeakOrdering comp - obiekt funkcyjny porównujacy dwa elementy (w przypadku użycia wersji z predykatem)

W wyniku działania obu funkcji zwracany jest iterator wskazujący na element badanego zbioru. W wypadku „lower_bound” wskazywana jest pierwsza pozycja, na ktorą należy wstawić zadany element, aby nie zaburzyć posortowanego ciągu. „upper_bound” zwraca ostatnią taką pozycję.

lower_bound(first, last, value [, comp])

analogicznie dla upper_bound

Algorytm przeszukuje dane w zakresie [first;last). Dla poprawnego działania należy podać iteratory na pierwszy element ciągu przeszukiwanego oraz na pierwszy element za ostatnim do przeszukiwania. Jako value należy podać obiekt klasy elementów zamieszczonych w przeszukiwanym ciągu. Prosty przykład użycia:

#include <vector>
#include <algorithm>
 
int main()
{
	std::vector<int> liczby;
	for(int i=0;i<10;++i)
		liczby.push_back(i);
	std::vector<int>::iterator iter;
	iter = lower_bound(liczby.begin(),liczby.end(),3);
	return 0;
}

Wersja z predykatem wymaga podania jako czwartego argumentu obiektu funkcyjnego służącego do porównywania danych obiektów. Przykład użycia:

#include <vector>
#include <algorithm>
 
 
class rowne
{
public:
	bool operator()(const int &a, const int &b)
	{
		return ( a < b) ? true : false;
	};
};
 
int main()
{
	std::vector<int> liczby;
	for(int i=0;i<10;++i)
		liczby.push_back(i);
	std::vector<int>::iterator iter;
	iter = lower_bound(liczby.begin(),liczby.end(),3,rowne());
	return 0;
}

Δ Algorytmy wymagają posortowanych zbiorów. Działanie na danych nieposortowanych może być źródłem błędów.

Δ Wersja bez predykatu wymaga do działania operator < dla klasy umieszczonej w zbiorze.

Δ Wersja z predykatem wymaga danych posortowanych przy użyciu tego predykatu.

upper_lower_bound.cpp