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})
Примеры

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int p;
    int a[] = {-1, 4, 2, 3, 7, 8, -5, 3, 11, -9};
    vector  <int> 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++