lower_bound

Структуры и функции   23 января 2012  Автор статьи:  

Пусть имеется контейнер, упорядоченный на полуинтервале [first, last). Тогда значением функции является итератор, указывающий на первый элемент из данного диапазона, который больше или равен заданному значению value. Если в заданном промежутке такого элемента нет, то функция возвращает итератор last в качестве значения.
Библиотека
stdlib.h
Способы вызова функции
ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value );
ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );
Где

  • first — итератор, указывающий на начало промежутка, в котором осуществляется поиск
  • last — итератор, указывающий на правую границу (не включительно) промежутка поиска
  • value — значение, относительно которого осуществляется поиск большего или равного элемента
  • comp — компаратор, согласно которому была произведена сортировка контейнера в заданном промежутке

Сложность
Функция имеет логарифмическую сложность от длины промежутка поиска.O(n\times\log{n})
Примеры

#include
#include
#include
using namespace std;

int main()
{
int p;
int a[] = {-1, 4, 2, 3, 7, 8, -5, 3, 11, -9};
vector v (a, a + 10);

sort (a, a + 10);
sort (v.begin(), v.end());

//После сортировки массив и вектор приняли вид
// -9 -5 -1 2 3 3 4 7 8 11

p = *lower_bound (a, a + 10, -3);
//Значением переменной p будет число -1

p = *lower_bound (v.begin(), v.end(), 3);
//Значением переменной p будет число 3
//причем итератор будет указывать на первое вхождение числа 3 в вектор

p = *lower_bound (v.begin(), v.end(), 12);
//Такое выражение вызовет Runtime Error, так как в массиве все числа строго меньше 12
//lower_bound вернет итератор, равный v.end(), указывающий на несуществующий элемент

return 0;
}

Замечания

Функция часто применяется для нахождения числа элементов массива, строго меньших данного.
Эту величину можно вычислить как int (lower_bound (first, last, value) — first).
Упорядоченный контейнер set имеет встроенную функцию lower_bound, но так как итераторы контейнера set нельзя вычитать, то предыдущее замечание в этом случае неверно.

Научиться программировать

  • на Delphi

  • на Java

  • на C++