On Fri, Jan 19, 2024 at 12:19 PM Iúri Chaer via Std-Proposals
<std-proposals_at_[hidden]> wrote:
>
> The current complexity guarantee for std::lower_bound states "At most log(last - first)+O(1) comparisons and projections" for all iterator types, pretty much enforcing the use of vanilla binary search, even if with non-random-access iterators that means 2*n iterator mutations. I've recently had a libc++ proposal for using one-sided binary search to reduce that cost to n iterator mutations rejected (https://github.com/llvm/llvm-project/pull/75230#issuecomment-1852637040), because it meant that we'd have at most 2*log(n) comparator calls. I have a strong feeling that this is not what the committee had intended.
>
> The solution from that proposal would have had a potentially interesting impact even for random-access iterators, because, although the average complexity is log(n) comparisons, it ranges from a single comparison to 2*log(n), and you can do a sequential scan in O(n) instead of the O(n*log(n)) that vanilla binary search would yield. It's not completely clear to me which would be more interesting in general, perhaps allowing implementors to decide even for random access iterators would be a good thing.
>
> What do you think of the idea of loosening the std::lower_bound comparator complexity requirements for non-random iterators to allow changes like the one I proposed?

I feel like reducing the potential number of iterations for
non-random-access iterators at the expense of potentially increasing
the projection/comparison count is something that should be relegated
to a different function. If you want a one-sided binary search, that's
something you should ask for. It shouldn't be imposed upon you by an
implementation which thinks it knows better in some scenario.