The paragraph 25.5.3 [alg.binary.search] in
http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2009/n2914.pdf
specifies the following complexity constraints (formatting omitted):
lower_bound: At most log2(last-first)+O(1) comparisons
upper_bound: At most log2(last-first)+O(1) comparisons
equal_range: At most 2*log(last-first)+1 comparisons

I think that "At most 2*log2(last-first)+O(1) comparisons" for
equal_range would be more consistent..

I suggest to be more exact and specify:
lower_bound: At most log2(last-first)+1 comparisons
upper_bound: At most log2(last-first)+1 comparisons
equal_range: At most 2*log(last-first)+2 comparisons

Or was the constraint for equal_range intentionally more strict
than what would result from calling both lower_bound and upper_bound?

If yes, do we expect implementers to let equal_range decide
by one call to a compare operator which of the possible three
outcomes of equal_range(first, first+1, value) to return?

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 9 Jul., 19:52, MathGis <mtahilfer...@hotmail.com> wrote:
> The paragraph 25.5.3 [alg.binary.search] inhttp://www.open-std.org/JTC1/SC22/WG21/docs/papers/2009/n2914.pdf
> specifies the following complexity constraints (formatting omitted):
> lower_bound: At most log2(last-first)+O(1) comparisons
> upper_bound: At most log2(last-first)+O(1) comparisons
> equal_range: At most 2*log(last-first)+1 comparisons
>
> I think that "At most 2*log2(last-first)+O(1) comparisons" for
> equal_range would be more consistent..
>
> I suggest to be more exact and specify:
> lower_bound: At most log2(last-first)+1 comparisons
> upper_bound: At most log2(last-first)+1 comparisons
> equal_range: At most 2*log(last-first)+2 comparisons
>
> Or was the constraint for equal_range intentionally more strict
> than what would result from calling both lower_bound and upper_bound?

There exist a LWG defect:

http://home.roadrunner.com/~hinnant/issue_review/lwg-defects.html#384

which resulted in the complexity requirement

2*log2(last - first) + O(1)

for equal_range. Since this one hasn't been changed as
you notice, it is an editorial problem. Please send a
corresponding report to

editorial at versatilecoding dot com

Greetings from Bremen,

Daniel Kr   gler



--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]