Алгоритм lower_bound()

Алгоритм 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 );

// отсортировать в порядке возрастания ...

sort( ivec.begin(), ivec.end(), greaterint() );

search_value = 26;

vector int, allocator ::iterator iter;

// необходимо указать, как именно

// осуществлялась сортировка ...

iter = lower_bound( ivec.begin(), ivec.end(),

search_value, greaterint() );

// печатается:

// Первый элемент, перед которым можно вставить 26, - это 26

// Предыдущее значение равно 29

cout "Первый элемент, перед которым можно вставить "

search_value

", - это "

*iter endl

"Предыдущее значение равно "

*(iter-1) endl;

return 0;

}