Searching string for character in binary search

[Steven Schveighoffer]

On 2/25/18 4:32 PM, Seb wrote:
> 
> Also note that Phobos comes with binary search built-in:
> 
> ---
> assert([1,2,3,4,5,6,7,8,9,10,11].assumeSorted.canFind(6));
> ---
> 
> https://run.dlang.io/is/bfpBpA

canFind (and find) works even on non-sorted ranges, so it's not the 
greatest proof. But it's good to know that it does work and uses a 
binary search!

You can see that it only does a few comparisons with something like:

https://run.dlang.io/is/lax6YP

Also, strings are not doing what you think:

"abcd".find('c'); // OK, linear search
"abcd".assumeSorted.find('c'); // Error
"abcd".assumeSorted.find("c"); // OK, but does NOT do a binary search!
[1,2,3,4].assumeSorted.find([3]); // OK, but also does not do a binary 
search!

My knee-jerk reaction is to blame auto-decoding ;) But maybe it's just a 
bug.

If you want to guarantee a binary search (i.e. compiler error when it 
cannot do it), you need to use SortedRange.lowerBound.

-Steve