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