lower_bound

Синтаксис:

    #include <algorithm>
    forward_iterator lower_bound( forward_iterator first, forward_iterator last, const T& val );
    forward_iterator lower_bound( forward_iterator first, forward_iterator last, const T& val, CompFn f );

Функция lower_bound - это разновидность бинарного поиска. Эта функция ищет первое место в упорядоченном диапазоне, определенном итераторами first and last, куда можно вставить значение val, сохраняя упорядоченность. Эквивалентная функция возвращает итератор на первый элемент, не являющийся меньшим, чем val, либо возвращает итератор end, если все элементы диапазона меньше чем val.

Функция работает только с упорядоченными диапазонами.

Возвращаемое значение функции lower_bound - это итератор, указывающий на место, куда можно безопасно вставить значение val. Если не задана функция сравнения f, для упорядочивания используется оператор <.

Например, следующий код использует lower_bound, для вставки числа 7 в упорядоченный вектор:

   vector<int> nums;
   nums.push_back( -242 );
   nums.push_back( -1 );
   nums.push_back( 0 );
   nums.push_back( 5 );
   nums.push_back( 8 );
   nums.push_back( 8 );
   nums.push_back( 11 );
 
   cout << "Before nums is: ";
   for( unsigned int i = 0; i < nums.size(); i++ ) {
     cout << nums[i] << " ";
   }
   cout << endl;
 
   vector<int>::iterator result;
   int new_val = 7;
 
   result = lower_bound( nums.begin(), nums.end(), new_val );
 
   nums.insert( result, new_val );
 
   cout << "After, nums is: ";
   for( unsigned int i = 0; i < nums.size(); i++ ) {
     cout << nums[i] << " ";
   }
   cout << endl;

Этот код производит следующий вывод:

   Before nums is: -242 -1 0 5 8 8 11
   After, nums is: -242 -1 0 5 7 8 8 11

lower_bound работает за логарифмическое время для контейнеров, которые поддерживают случайный доступ, и за линейное время для остальных контейнеров. Эта функция совершает O(log n) сравнений.

Смотрите также: binary_search, equal_range, upper_bound