Binary Search in D 2.0 (Phobos)?

Question

Is it just me, or is there no binary search function in Phobos? I have a pre-sorted array that I want to search with my own comparator function, but I can't find anything in std.algorithms or std.containers.

Thanks!

Oloughlin

Answer 1

Use SortedRange from std.range:

Cribbed from http://www.digitalmars.com/d/2.0/phobos/std_range.html#SortedRange:

auto a = [ 1, 2, 3, 42, 52, 64 ];
auto r = assumeSorted(a);
assert(r.canFind(3));
assert(!r.canFind(32));

Heimlich

Ah, you have to use "assumeSorted"... didn't expect that, thanks! :) – Oloughlin

find() (and thus canFind()) is actually pretty smart, using different algorithms based on what type input its given. In order for binary search to work, the data has to be sorted, so assumeSorted() makes it so that it is, and then find() and canFind() are smart enough to know that binary search is the best search then, and that's what they do. – Robey

It's not intuitive at all though if you are simply trying to do a binary search. – Furtek

It's late and I'm tired, but I suspect the design is good, I mean, it seems cool to bring strong typing to the concept of sortedness, and to separate 'what you want to do' from 'how it gets done'. D just needs a solid body of questions and answers like this one so that people can learn these things quickly with Google. – Beni