.. Algorithms/Querying Algorithms//lower_bound |60

lower_bound
===========

Synopsis
--------

.. parsed-literal::
    
    template<
          typename Sequence
        , typename T
        , typename Pred = less<_1,_2>
        >
    struct lower_bound
    {
        typedef |unspecified| type;
    };



Description
-----------

Returns the first position in the sorted ``Sequence`` where ``T`` could be inserted without 
violating the ordering.


Header
------

.. parsed-literal::
    
    #include <boost/mpl/lower_bound.hpp>


Parameters
----------

+---------------+-------------------------------+-----------------------------------+
| Parameter     | Requirement                   | Description                       |
+===============+===============================+===================================+
|``Sequence``   | |Forward Sequence|            | A sorted sequence to search in.   |
+---------------+-------------------------------+-----------------------------------+
|``T``          | Any type                      | A type to search a position for.  |
+---------------+-------------------------------+-----------------------------------+
|``Pred``       | Binary |Lambda Expression|    | A search criteria.                |
+---------------+-------------------------------+-----------------------------------+


Expression semantics
--------------------

For any sorted |Forward Sequence| ``s``, binary |Lambda Expression| ``pred``, and
arbitrary type ``x``:


.. parsed-literal::

    typedef lower_bound< s,x,pred >::type i; 

:Return type:
    |Forward Iterator|.

:Semantics:
    ``i`` is the furthermost iterator in |begin/end<s>| such that, for every iterator 
    ``j`` in [``begin<s>::type``, ``i``),
    
    .. parsed-literal::
    
        apply< pred, deref<j>::type, x >::type::value == true



Complexity
----------

The number of comparisons is logarithmic: at most log\ :sub:`2`\ ( ``size<s>::value`` ) + 1. 
If ``s`` is a |Random Access Sequence| then the number of steps through the range 
is also logarithmic; otherwise, the number of steps is proportional to 
``size<s>::value``.


Example
-------

.. parsed-literal::
    
    typedef vector_c<int,1,2,3,3,3,5,8> numbers;
    typedef lower_bound< numbers, int_<3> >::type iter;

    BOOST_MPL_ASSERT_RELATION( 
          (distance< begin<numbers>::type,iter >::value), ==, 2
        );
    
    BOOST_MPL_ASSERT_RELATION( deref<iter>::type::value, ==, 3 );


See also
--------

|Querying Algorithms|, |upper_bound|, |find|, |find_if|, |min_element|


.. copyright:: Copyright ©  2001-2009 Aleksey Gurtovoy and David Abrahams
   Distributed under the Boost Software License, Version 1.0. (See accompanying
   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)