Return an iterator positioned at the first position in the range [ first ... last ) that value can be inserted without violating the order of the collection. If no such position exists, return last . The first version assumes that the elements are already sorted using operator< , whereas the second version assumes that the elements are already sorted using the binary function compare .

Declaration


  
#include <algorithm>

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 compare
  );

Complexity

Time complexity is O(log(N)) for random access iterators and O(N) for all other iterators. Space complexity is constant.

Example <ospace/osstd/examples/lwrbnd1.cpp>


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

void
main()
  {
  vector< int > v1( 20 );
  for ( size_t i = 0; i < v1.size(); ++i )
    {
    v1[ i ] = i/4;
    cout << v1[ i ] << ` `;
    }

  int* location =  lower_bound( v1.begin(), v1.end(), 3 );

  cout
    << "\n3 can be inserted at index: "
    << ( location - v1.begin() )
    << "\n";
  }

0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
3 can be inserted at index: 12

Example <ospace/osstd/examples/lwrbnd2.cpp>


    #include <iostream>
#include <string.h>
#include <algorithm>

char* str[] = { "a", "a", "b", "b", "q", "w", "z" };

bool
char_str_less( const char* a_, const char* b_ )
  {
  return ::strcmp( a_, b_ ) < 0 ? 1 : 0;
  }

void
main()
  {
  const unsigned str_ct = sizeof( str )/sizeof( str[ 0 ] );
  cout
    << "d can be inserted at index: "
    << ( lower_bound
          (
          str,
          str + str_ct,
          "d",
          char_str_less
          )
          - str
       )
    << "\n";

  }

d can be inserted at index: 4

lower_bound

Library

Declaration

Complexity

Example <ospace/osstd/examples/lwrbnd1.cpp>

Example <ospace/osstd/examples/lwrbnd2.cpp>