Алгоритм lower_bound()
template< class ForwardIterator, class Type >
ForwardIterator
lower_bound( ForwardIterator first,
ForwardIterator last, const Type &value );
template< class ForwardIterator, class Type, class Compare >
ForwardIterator
lower_bound( ForwardIterator first,
ForwardIterator last, const Type &value,
class Compare );
lower_bound() возвращает итератор, указывающий на первую позицию в отсортированной последовательности, ограниченной диапазоном [first,last), в которую можно вставить значение value, не нарушая упорядоченности. В этой позиции находится значение, большее либо равное value. Например, если дана такая последовательность:
int ia = = {12,15,17,19,20,22,23,26,29,35,40,51};
то обращение к lower_bound() с аргументом value=21 возвращает итератор, указывающий на 23. Обращение с аргументом 22 возвращает тот же итератор. В первом варианте алгоритма используется оператор “меньше”, определенный для типа элементов контейнера, а во втором для упорядочения элементов применяется объект comp.
#include <algorithm>
#include <vector>
#include <iostream.h>
int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
sort( &ia[0], &ia[12] );
int search_value = 18;
int *ptr = lower_bound( ia, ia+12, search_value );
// печатается:
// Первый элемент, перед которым можно вставить 18, - это 19
// Предыдущее значение равно 17
cout << "Первый элемент, перед которым можно вставить "
<< search_value
<< ", – это "
<< *ptr << endl
<< "Предыдущее значение равно "
<< *(ptr-1) << endl;
vector< int, allocator > ivec( ia, ia+12 );
// отсортировать в порядке возрастания ...
