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

upper_bound

for_each  |  lower_bound  |  upper_bound
Тут лежит определение функции

Тут описание


 

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

 

Замечание 2.2

 

Параметры

имя параметра
описание параметра

 

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


 

Пример.

#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 = upper_bound(myArray, myArray + 10, 5);
    cout << "upper_bound of 5 in array is " << five - myArray << " and value is " << *five << endl;

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

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

    return 0;
}
 


Результат:

upper_bound of 5 in array is 5 and value is 6
upper_bound of 5 in vector is 4 and value is 6
There is no value greater than 10 in vector

 

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

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

 


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