As Andreas refines the idea, I'm starting to like it.

It seems like the primitive operation being described here is something like... It takes a range and returns an iterator `mid` such that [first, mid) has at least one element, but where the implementation is encouraged to attempt to make [first, mid) and [mid, last) roughly equal in size, when possible. This is the operation you want for binary-search, or any divide-and-conquer algorithm (e.g. QuickSelect).

Notice that in C++20 Ranges, you probably want it to return not just the iterator but a **pair of subranges**, because in Ranges, a subrange is permitted to carry its size along with it, and we want to permit the possibility of returning sized subranges here.

I observe that std::lower_bound(first, last, value) is currently implemented in terms of std::next/std::advance, whereas it could actually be faster (on subranges of a `std::set`, at least) if it used this `divide_range` primitive at each step instead of trying to do the exact math.

But, if you switch std::lower_bound to use `divide_range`, and if `divide_range` for linked-list iterators is just std::next, then the performance of std::lower_bound would get *worse *on subranges of std::list, because you'd basically change a pointer-chasey binary search into a pointer-chasey linear search.

I think the conclusion there is that `divide_range` for linked-list iterators must **not **be std::next. For arbitrary iterators it should still return `first + std::distance(first, last)/2`, even though that takes O(n) to compute.

Anyway, I think there's something here. It feels very STL-ish to me. But I suspect that it's "STL from a parallel universe" where C++20 never happened and even C++98 made a couple of choices differently. I still can't really see it standing a chance in today's Standard.

my $.02,

–Arthur