Записки программиста
Авторский блог Михаила Лукина

lower_bound

for_each  |  lower_bound  |  upper_bound
template <class ForwardIterator, class T> ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value );
template <class ForwardIterator, class T, class Compare> ForwardIterator lower_bound ( ForwardIterator first, ForwardIterator last, const T& value, Compare comp );

Возвращает итератор, указывающий на первый элемент в сортированном интервале [first; last), который не меньше, чем value. Для сравнения элементов используется либо оператор < (в первой версии), либо функция comp (во второй версии).


 

Замечание 1. Следует обратить внимание на то, что интервал должен быть отсортирован.

 

Замечание 2. В отличие от upper_bound значение, на которое возвращается указатель, может быть равно value.

 

Параметры

first, last
Итераторы на начало и конец интревала.
value
Значение, с которым сравниваются элементы интервала.
comp
Функция сравнения.

 

Возвращаемое значение

Итератор на нижнюю границу в интервале для значения value. В случае, если value больше, чем все элементы интервала, возвращается last

 

Пример.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main(int argc, char **argv)
{
    int myArray[10] = {1, 2, 3 ,4, 5, 6, 7, 8 , 9, 10};
    vector<int> myVector(myArray + 1, myArray + 9);

    const int *five = lower_bound(myArray, myArray + 10, 5);
    cout << "Position of 5 in array is " << five - myArray << " and value is " << *five << endl;

    vector<int>::iterator iter1 = lower_bound(myVector.begin(), myVector.end(), 5);
    cout << "Position of 5 in vector is " << iter1 - myVector.begin() << " and value is " << *iter1 << endl;

    vector<int>::iterator iter2 = lower_bound(myVector.begin(), myVector.end(), 10);
    if (iter2 == myVector.end())
    {
        cout << "There is no value 10 in vector" << endl;
    }

    return 0;
}
 


Результат:

Position of 5 in array is 4 and value is 5
Position of 5 in vector is 3 and value is 5
There is no value not less 10 in vector

 

Временная сложность

Производит O(log(n)) сравнений, где n - числов элементов интервала. Производит O(n) шагов по итераторам. Общее время работы O(n). Для итераторов произвольного доступа числов шагов сокращается до O(log(n)), и, следовательно, общее время работы O(log(n)).

 

Версия для печати

© 2010-2014. Записки программиста. Все права защищены.
Яндекс.Метрика
ВебСтолица.РУ: создай свой бесплатный сайт!  | Пожаловаться  
Движок: Amiro CMS