Sorted Collection Protocol

[kareman (Kare Morstol)]

@nnnnnnnn

I think you would need to pass the count as an argument to avoid the repeated calculation if you keep the recursive version of this. An iterative version wouldn’t have that issue, but you’d need to track the index movements another way.

I implemented both here. As you'd expect the non-recursive version is fastest on the random access collection SortedArray (both axes are logarithmic):

When it comes to using binary search on non-random access collections it seems the built-in start-from-the-beginning-and-check-every-element is faster, at least with DefaultIndices<String>:

All the code is available here.