>> Personally I'd prefer something like this to have a name that told me
>> what algorithm it actually is, e.g. one_sided_lower_bound.

Iúri Chaer wrote:
> Wouldn't that go counter to the design philosophy of the STL? lower_bound
> is not the name of an algorithm, but of the action -- the algorithm behind
> it in all the mainline implementations is the classic binary search, but
> that's not explicit in its name.

I don't want to get into a deep discussion about naming, but my personal
preference is generally more towards using the accepted names of
algorithms or data structures that we might find in textbooks, hence
my use of "personally" in the quote above. Others will differ.

But in the case of your proposal, an important consideration is that
both classic binary search and one-sided binary search are useful for
random-access containers, in different situations. If both exist they
need different names. Classic binary search already has a name, so
one-sided needs a different name.

Doing any sort of binary search in an ordered std::list, or similar,
is IMHO a somewhat exotic thing to want to do. Some might be surprised
to discover that std::lower_bound and especially std::binary_search work
at all with non-random-access iterators. You could even argue that it's
dangerous for it to support data structures where its performance is
linear rather than logarithmic, i.e. it would be better for the user to
get an error or warning telling them to change their list to a vector,
or to just do a std::find linear search.

The reduced number of iterator increments that you report (n rather
than 2n) is due to the classic binary search algorithm needing to
find the length of the range when it starts. But in the case of
std::list since C++11 we have constant-time size(), which
std::lower_bound() doesn't exploit. Does
std::ranges::lower_bound<std::list> do so? Using this would give n
iterator mutations and log(n) comparisons, I think. Are there
particular containers / iterators that you are interested in where
the size of the range is not available in constant time?


> I'd
> be happy if the wording for the lower_bound guarantees were loosened to
> allow the use of algorithms with better overall complexity. Perhaps it
> could say something like "at most log(last - first)+O(1) comparisons for
> random-access iterators, or O(log(last - first)) comparisons for other
> iterator types".

I wouldn't object to that specific change, if you had benchmarks showing
an improvement for some non-contrived use case.


Regards, Phil.