Find on sorted range slower?

[Tofu Ninja via Digitalmars-d-learn]

On Friday, 7 August 2015 at 10:01:39 UTC, Timon Gehr wrote:
> On 08/07/2015 11:03 AM, Tofu Ninja wrote:
>> On Friday, 7 August 2015 at 08:18:04 UTC, Nordlöw wrote:
>>> On Friday, 7 August 2015 at 05:21:32 UTC, Tofu Ninja wrote:
>>>> HAHAH wow, this is hilarious, I just checked, nothing in 
>>>> std.algo
>>>> takes advantage of sorted ranges, sort doesn't even take 
>>>> advantage of
>>>> it! You pass a sorted range into sort and it will just 
>>>> resort it!
>>>> Wow....
>>>
>>> Who fixes this?
>>>
>>> I can look into it... is there an issue for this?
>>
>> I have no idea, but it is pretty silly. Sort/isSorted on a 
>> sorted range
>> should be a nop. Find and friends, should do doing some kind 
>> of binary
>> search. Max and min should be O(1). Some of the functions that 
>> return a
>> sub range or a mutated range could probably be returning 
>> sorted ranges
>> as well if its input is a sorted range, remove, strip and 
>> split at least
>> could.
>
> Binary search is not always faster than linear search.

It will be for the majority of sorted ranges. Though if other 
searches are needed, find and friends could take an extra arg 
SearchPolicy for sorted ranges that defaults to binary search.