On Tuesday, 15 May 2012 at 17:23:28 UTC, Kirill wrote:
How about users who don't know what binary search is. binary
search is an intuitive concept for people who have good
programming experience but assumeSorted(r).contains(x) is more
intuitive to higher level users.
If you don't know about binary search, you won't write
assumeSorted(r).contains(x) you'll just write r.contains(x)
because you have no idea that binary search exists. Why would you
bother typing extra characters for a benefit that you are unaware
of?
If you do know that binary search exists then the obvious
algorithm name is binarySearch. If I use .contains to coax a
binarySearch then I'm relying on a little bit of faith. In what
situations does it give a binary search?
[1, 2, 3].contains(2); // does the compiler infer that 1, 2, 3 is
sorted?
iota(10).contains(5); // is iota implicitly a sorted range?
assumeSorted([1, 2, 3]).map!(x => x + 1).contains(3); // does
Phobos know that the map is order preserving?
assumeSorted([1, 2, 3]).filter!("a & 1").contains(2); // does
Phobos know that filters always preserve order?
I'd have to read the documentation to find out which of these
uses binary search. In fact, I'd probably have to read the Phobos
source.
If I just used binarySearch then I would be 100% guaranteed that
it will use a binary search. I don't have to second guess the
compiler -- I just *know*.
