Opportunistic worst-case complexity upgrade? aka binary search with `find`

[Jonathan M Davis via Digitalmars-d]

On Thursday, 24 July 2014 at 01:26:48 UTC, Jakob Ovrum wrote:
> On Thursday, 24 July 2014 at 01:21:44 UTC, Jakob Ovrum wrote:
>> -snip-
>
> Another point is that the range types of the two currently 
> available sorted containers - RedBlackTree and BinaryHeap - are 
> *not* instances of SortedRange. If algorithms working on sorted 
> ranges become a thing, it seems like they should be.

Maybe a better approach would be do just have sorted range types 
define find themselves? UFCS would then make it so that the best 
search function for that type would be used (e.g. I don't think 
that binary search is the best method to use a red-black tree).

However, regardless of that, it could be useful to know whether a 
range is sorted or not in general, and we may want to change how 
we do that so that there's an enum which indicates it rather than 
simply wrapping it in SortedRange (e.g. we know that 
RedBlackTree's range type is sorted, but I doubt that we want to 
always be wrapping it in a SortedRange to show that).

- Jonathan M Davis