2 Copyright 2010 Neil Groves
3 Distributed under the Boost Software License, Version 1.0.
4 (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 [section:lower_bound lower_bound]
15 typename range_iterator<ForwardRange>::type
16 lower_bound(ForwardRange& rng, Value val);
19 range_return_value re,
23 typename range_return<ForwardRange, re>::type
24 lower_bound(ForwardRange& rng, Value val);
31 typename range_iterator<ForwardRange>::type
32 lower_bound(ForwardRange& rng, Value val, SortPredicate pred);
35 range_return_value re,
40 typename range_return<ForwardRange,re>::type
41 lower_bound(ForwardRange& rng, Value val, SortPredicate pred);
46 The versions of `lower_bound` that return an iterator, returns the first iterator in the range `rng` such that:
47 without predicate - `*i < value` is `false`,
48 with predicate - `pred(*i, value)` is `false`.
50 `end(rng)` is returned if no such iterator exists.
52 The versions of `lower_bound` that return a `range_return`, defines `found` in the same manner as the returned iterator described above.
56 Defined in the header file `boost/range/algorithm/lower_bound.hpp`
58 [heading Requirements]
60 [*For the non-predicate versions:]
62 * `ForwardRange` is a model of the __forward_range__ Concept.
63 * `Value` is a model of the `LessThanComparableConcept`.
64 * The ordering of objects of type `Value` is a [*/strict weak ordering/], as defined in the `LessThanComparableConcept` requirements.
65 * `ForwardRange`'s value type is the same type as `Value`.
67 [*For the predicate versions:]
69 * `ForwardRange` is a model of the __forward_range__ Concept.
70 * `BinaryPredicate` is a model of the `StrictWeakOrderingConcept`.
71 * `ForwardRange`'s value type is the same type as `Value`.
72 * `ForwardRange`'s value type is convertible to both of `BinaryPredicate`'s argument types.
74 [heading Precondition:]
76 [*For the non-predicate versions:]
78 `rng` is sorted in ascending order according to `operator<`.
80 [*For the predicate versions:]
82 `rng` is sorted in ascending order according to `pred`.
86 For ranges that model the __random_access_range__ concept the complexity is `O(log N)`, where `N` is `distance(rng)`.
88 For all other range types the complexity is `O(N)`.