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?


Cheers,
Iuri